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!)

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.