Big O notation
Contents
Big O notation¶
The Big O notation indicates how fast an algorithms is. It is the worst case evaluation of the given algorithms. In short, how many iterations are needed in the worst case.
O(n)
^ ^
| +-- Number of operations
+---- Big O
A list of algorithms with theirs Big O notation can be found at https://big-o.io.
Fig. 1 Source: https://big-o.io¶
Some common runtimes¶
\(O(log\;n)\) - also known as log time
\(O(n)\) - also known as linear time
Simple search
\(O(n\;*\;log\;n)\) - fast sorting algorithms
quicksort
\(O(n^2)\) - slow sorting algorihtms
selection sort
\(O(n!)\) - very slow algorithms
traveling salesperson
Fig. 2 Source: https://www.bigocheatsheet.com¶
Worst to Best¶
\(O(n!)\)
\(O(2^n)\)
\(O(n^2)\)
\(O(n(log(n))^2)\)
\(O(n log(n))\)
\(O(n)\)
\(O(k)\)
\(O(n+k)\)
\(O(nk)\)
\(O(log(n))\)
\(O(1)\)