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(2n) (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(n2) (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:
- Both data structures store lists of
n
elements, and both their methods get
are used to access a position element index
.
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.
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.
I have to confess that the definition "scientific" is the simplest and accurate that I know. What difficulty are you having with her?
– hugomg
The question is good but I won’t risk answering because it’s not easy to hit her target, her focus is not the content but the form. For those who do not know have a famous question in the OS about this. And even translate one of these answers I do not know if it would solve. I don’t know if this is so simple: http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o
– Maniero
Possible is, I just don’t think I should do.
– Maniero
Related: "What is the complexity of an algorithm?"
– mgibsonbr
This is the kind of question that makes your mouth water :D.
– Cold
@bigown will not answer, just because the question has almost his name?
– Wallace Maxters
Big O means that the function (number of operations) is limited: For example: O(e n), it means that there is a number (alpha) that limits this function: the number of operations is always less than alpha*e n. The analysis O() does not take into account the alpha value, it only says that it exists. O(2.e n) = O(e n) (factor the constant that joins the alpha). Some algorithms are quite optimized, but sometimes it is possible to minimize the alpha value.
– user178974