What is Big O

Calculating the complexity of an algorithm.

Some algorithms scale well with growing inputs.

• Some scale poorly with growing input.

Other metrics

Big O

• Worst-case time complexity of an algorithm
• alphabet O, not zero 0

Omega Notation (Ω).

• Best-case time complexity of an algorithm

Theta Notation (Θ)

• Average-case time complexity of an algorithm

Ranking of Big O

From the most efficient to least efficient:

n = number of inputs.

constant time O(1)
logarithmic O(log n)
linear O(n)
Linearithmic O(n log n)
Quadratic O(n^2)
Exponential O(2^n)
Factorial O(n!)

Amortized Time

Average time taken in total when operation is repeated many times.

• Ignores worst-case or the best-case of that operation.

If you run an operation million times and the operation runs very slow/fast once in a while (and is extremely rare), you exclude/dilute the outlier.

An example of this would be a dynamic resizing of an array in memory.

In terms of notation, amortized time is indicated with a + at the end: O(n)+ instead of O(n).

Deep Dive

Constant is always the same amount of time regardless of input size.

• 1 input or 10,000,000 input take same time

Linear is scales linearly with the input size.

• 1 input takes one second, 600 inputs take 10 minutes

Quadratic scales as exponent of 2

• 4 items take 16 seconds; 10 items take 100 seconds.