Definition of the "Big O" notation

Question

In discussions about algorithmic performance, the use of notation is very common Big O:

O(1), O(n), O(n²)

It is easy to find the scientific definition of this notation and it is easy to find some more informal definitions in English.

What I ask here is an informal definition of this notation, which is immediately useful even for the least versed in mathematics.

I will try to formulate an example to bring up the definition of Big O for the practical:

Studying the list implementations Arraylist and Linkedlist (Java), it is said that one of the differences between them is that the method Arraylist.get(int index) is O(1) as the method Linkedlist.get(int index) is O(n) but in practice, what the notation Big O is indicating in this case?

Of course other practical examples are welcome.

Answer 1

Here’s an informal (and visual).

The idea of notation Big-O is to describe the overall behavior (also called asymptotic, as it is the behavior at the boundary as data grows) of the algorithm in terms of the growth of the number of operations as the number of processed elements grows (the quantity of items is described in general by n).

The idea is to use the lyrics The followed by a function on n to describe this growth of the algorithm. The faster the number of operations to process items grow, the "worse" the performance of the algorithm (because it performs more instructions and therefore takes longer - it is "more complex").

The charts below (recreated quickly in Excel) illustrate the most common growth curves. The first has an overview, and the second is a smaller view (Y-axis with less values) to display more clearly the "best" growth curves: O(1) and O(log n).

From these graphs it is possible to notice that:

• In a complexity algorithm O(n!) (factorial) the number of executed instructions grows very quickly for a small growth in the number of processed items. Among the illustrated is the worst behavior for an algorithm, as processing quickly becomes unviable. This is the case of the innocent implementation of Problem of the Traveling Salesman or an algorithm that generates all possible permutations of a list, for example (source of this example).

• A complexity algorithm O(2ⁿ) (exponential) is also very bad, because the number of instructions also grows very quickly (exponentially), although at a lower rate than the previous one. This is the case of algorithms that search in unordered binary trees, for example.

• A complexity algorithm O(n²) (quadratic) is feasible, but tends to become very bad when the amount of data is large enough. This is the case of algorithms that have two ties (for) chained, such as the processing of items in a two-dimensional matrix.

• A complexity algorithm O(n log n) (sub-quadratic or super-linear) is better than quadratic, being generally as far as it can optimize algorithms that are quadratic in their most direct and innocent implementation (naïve). This is the case for the sorting algorithm Quicksort, for example (which has this complexity in the average case, but which is still quadratic in the worst case).

• A complexity algorithm O(n) (linear) is one whose growth in the number of operations is directly proportional to the growth in the number of items. This is the case of searching algorithms in an unordered one-dimensional matrix, for example.

• A complexity algorithm O(log n) (logarithm) is the one whose growth in the number of operations is smaller than the number of items. This is the case of ordered binary tree search algorithms (Binary Search Trees), for example (in the average case, in the worst case it remains linear).

• A complexity algorithm O(1) (constant) is the one where there is no growth in the number of operations, as it does not depend on the volume of input data (n). This is the case of direct access to an element of a matrix, for example.

So in your final question:

which means to say that ArrayList.get(int index) is O(1) whereas LinkedList.get(int index) is O(n)?

One can understand the following:

1. Both data structures store lists of n elements, and both their methods get are used to access a position element index.
2. ArrayList.get(int index) has complexity O(1) because it probably gives direct access to the memory position of the element (such as a one-dimensional matrix via operator []) or uses a scatter table (hash table) to locate it quickly. That is, it makes the access with 1 single operation.
3. LinkedList.get(int index), On the other hand, you need to navigate item by item from the first item to access the desired item. This is because the structure of a linked list has only the pointer to the first element, which points to the next, and this points to the next, and so on. As in the worst case all items will need to be accessed (if the desired item is the last, this is, index = n), the complexity of the algorithm is O(n). That is, it makes the access with n operations.

Compare the two data structures only for the complexity of this method get is wrong, because although access to an item is faster with the first, deleting or adding an item in the middle of the list is faster with the second - since it is not necessary to copy/move n-1 elements, simply modify the links (pointers) between the items. Thus, in general this comparison needs to be carried out having in mind the wider use that a certain data structure will have in another algorithm.

The original source of the graphics is the website http://bigocheatsheet.com/, which has complexity comparison matrices in the notation Big-O of different data structures and algorithms.

Note: Generally, when using the Big-O notation, it refers to the complexity of the running time algorithm (related to the number of instructions executed). But this same analogy can be made to describe the complexity of the algorithm in terms of space (such as the space of storage grows as the number of input data grows). In link referenced above can be noticed, for example, that the matrices indicate the complexity in time (Time Complexity) and in space (Space Complexity) for data structures and algorithms using the same notation.

Answer 2

It’s kind of hard to give an informal response to this kind of content, since it requires a knowledge of function limits, but I’ll try anyway:

Given two non-negative functions f(n) and g(n), whose n leads to infinity, we say that f = Ο(g), when, no matter how much n grow, g(n) will always be greater than or equal to f(n).

Example

If f(n) = n² and g(n) = n³, for all n positive, n³ will always be greater than n², that is to say, f = O(g) ( n² = O(n³) ).

Remarks

• If f(n) = 3n³ and g(n) = n³ we can say that f(n) = n³ and that f = O(g), as constants are usually omitted.

• We can also say that the function g(n) can be expressed as the higher power term in n of function f(n), that is, if f(n) = n 5 + n 4 + 6, we can say that g(n) = n 5, which is the term of greater power in n of f(n) and we can also say that f = O(g), that is to say, n 5 = O(n 5).

Leading to the complexity of algorithms:

If we have an array with n elements and we want to find the 3rd element (n = 3), we should travel 3 elements in the vector until it is found, thus a function to find the nnth element of the vector would be A(n) = n, in this way, we can say that g(n) = n, which implies that A = O(g), that is to say, A = O(n).

In general this means that, no matter the size of the vector, the "maximum number of operations" which will be performed in a search in the vector will be of order n.

I hope I helped and I didn’t confuse anyone :p

Answer 3

Definition in a sentence:

• Serves to compare how much of a resource is used by a algorithm that processes a collection, when the number of elements in this collection tends to be very large.

Analogy with hash-code:

• For those who have heard of hash-code... Big-O is as if it were an ordinable hash-code. Two distinct values have relative ordering. Two equal values have no relative ordering.

Highlighting:

• the measured resource is usually CPU time or busy memory (or anything related... such as number of operations)
• Big-O can be measured in different circumstances: cases more favorable, affairs median, affairs less favourable
• the algorithm input is a collection of variable size (with n elements)
• Comparison of Big-O ratings is only valid for collections with many elements
• generally algorithms try to balance the resources of CPU time and busy memory, then there is no better algorithm, but more appropriate for each situation

Examples:

• O(n) is always less than O(n²), when n grows beyond a certain value. Even if you multiply the first one, still this statement does not change: O(n*10000000) = O(n) < O(n²).

• Whether an algorithm processes a collection using memory O(n*log(n)) then it occupies less memory than another equivalent algorithm it uses O(n). Therefore, if memory is a lean feature, it is best to use the first one. Since they are equivalent, probably the first one will use more CPU and the second one less.

• For a few elements (e.g. 10, 100... depends on the algorithm) it is not possible to use Big-O notation to evaluate anything. In such cases you will need to parse the resource during execution. An algorithm whose CPU time is n² is faster than a 1000*n until n = 999, that is faster than a O(1) whose constant is 10,000,000.

• It is not possible to compare two algorithms whose Big-O are equal. Again it is necessary to have the exact formula in hand, or measure manually. An algorithm 10*n is better than a 100*n, but they both have O(n).

• Sometimes you are interested in the worst case of an algorithm, which is when it receives an input that causes the worst performance. For example, damped algorithms^{(in English)} use memory strategies to streamline successive operations... however these algorithms have variations that can become very bad, not being compatible with high-performance requirements. The goal of these algorithms is to improve the Big-O of the most common case.

• Other algorithms require a constant Big-O, for all cases. Often used in the production of hardware. A very interesting example are the Sorting Networks: sorting algorithms of O(1) invariable.