00 Votes

O-Notation

Article by Stefan Trost | Last update on 2023-01-18 | Created on 2012-02-05

The O-Notation, or otherwise also known as Landau symbols, are used in computer science to describe the asymptotic behavior of functions: That means, the O-Notation shows, depending on the input size, how many steps or calculations are required by the function.

Depending on how the operating expense changes with the input size, we can assign any function in computer science to one of the following classes:

O(1)The function does not exceed a constant value. The computation time is thus independent of the input size, eg when looking up an element in an array of an arbitrary size.
O(log x)If the argument doubles, the function grows with a constant amount. For example, a binary search in a sorted array.
O(√x)The function grows like the square root function and thus to about twice when the argument quadruples.
O(x)The growth is linear. If the argument doubles, also the function is doubled. For example in the linear search in an unsorted array.
O(xlogx)The growth is super-linear, such as with better search algorithms like mergesort.
O(x²)The growth is square. If the argument doubles, the function grows to four times, such as in simple algorithms for sorting numbers.
O(2^x)The function grows exponentially and thus with an increase of the argument of 1, the function doubles.
O(x!)The growth is factorial. The function grows by x+1 times, if the argument is incremented by 1.

Therefore, the O-Notation is almost an upper bound, how many operations are at a maximum necessary when using the function. Desired is usually the shortest possible processing time, so ideally O(1) or O(log x), although in practice, this is in most applications not possible.

Application and Examples

When programming a project, you should always think about the O-Notation Classes of the functions used to be able to find the bottleneck of the application.

This is important, for example, in the following use case: If we have two projects whose bottlenecks are O(x²) and O(2^x), in a test environment with 5 users, there will be no noticeable differences. Thereby, 25 or 32 operations are necessary, which is easily overcome by a computer. But, if 50 users are signed in, we are already at 2,500 or 1,125,899,906,842,624 calculations. No telling how quickly the system would be on the ground with an amount of 10,000 users on the system. The following table may illustrate this even further:

Input Size1101001.000
0(log x)1257
0(x)1101001.000
O(x²)110010.0001.000.000
O(2^x)110241,3*10^301,1*10^301
Exemplary, the table shows four different O-Notations with four different input sizes between 1 and 1,000. You can clearly see, that at a input size of 1, the class of function plays no role. But it then becomes interesting at a progressively increasing input size. Even input sizes of 10 and 100 have very significant effects. You may not want to imagine, how long you would have to wait at the automated cash dispenser, if searching your bank account data would follow O(2^x). Accordingly, using good algorithms is very important!

ReplyPositiveNegative

About the Author

AvatarYou can find Software by Stefan Trost on sttmedia.com. Do you need an individual software solution according to your needs? - sttmedia.com/contact
Show Profile

 

Related Topics

The Askingbox Search

Info | 0 Comments

Important Note

Please note: The contributions published on askingbox.com are contributions of users and should not substitute professional advice. They are not verified by independents and do not necessarily reflect the opinion of askingbox.com. Learn more.

Participate

Ask your own question or write your own article on askingbox.com. That’s how it’s done.