Big O Notation

O(1) = Constant-time = Time to execute an algorithm or operation doesn't depend on size of input
Getting or accessing array element is a constant-time operation.

Constant-time is sort of "dream come true" for an algorithm, the best!


O(log n) = Logarithmic time = Time to execute an algorithm or operation is proportional to logarithm of size of input n.
Binary search on a sorted list is logarithmic in complexity.


O(n) = Linear time = Time to execute an algorithm or operation depends on size of input n, or is directly proportional to size of input n
Determining smallest element in an unsorted array is a linear-time operation.
Determining smallest element in an unsorted, fixed-size array can be considered as a constant-time operation (since n is a constant in this scenario).

Linear time is desirable attribute of an algorithm!


O(n log n) = Log-linear time
Heap sorting is log-linear in nature.


O(n^k) = Polynomial time = Time to execute an algorithm or operation is no greater than a polynomial function of a constant k irrespective of size of input n.
O(n²) = Quadratic time
O(n³) = Cubic time

Polynomial time is considered "fast" (enough) for an algorithm.


O(kⁿ) = Exponential time = Time to execute an algorithm or operation is an exponential function of size of input n.

Exponential time is (considered) "slower" than polynomial time for an algorithm.