Complexity Analysis

Module 4.14 — Big-O growth curves and time estimates

Max n:

Growth Rate Comparison

01024204830724096016324864Input Size (n)

Time Estimates (at 10⁹ ops/sec)

nO(1)O(log n)O(n)O(n log n)O(n²)
1<1μs<1μs<1μs<1μs<1μs
2<1μs<1μs<1μs<1μs<1μs
4<1μs<1μs<1μs<1μs<1μs
8<1μs<1μs<1μs<1μs<1μs
16<1μs<1μs<1μs<1μs<1μs
32<1μs<1μs<1μs<1μs1μs
64<1μs<1μs<1μs<1μs4μs
128<1μs<1μs<1μs<1μs16μs

Complexity Classes

O(1)Constant
Array access, Hash lookup
O(log n)Logarithmic
Binary search, BST lookup
O(n)Linear
Linear search, Array sum
O(n log n)Linearithmic
Merge sort, Heap sort
O(n²)Quadratic
Bubble sort, Nested loops
O(n³)Cubic
Matrix multiply, Floyd-Warshall
O(2ⁿ)Exponential
Subsets, Naive Fibonacci

Big-O Rules

• Drop constants: 2n → O(n)
• Drop lower terms: n²+n → O(n²)
• Nested loops multiply: O(n·m)
• Sequential add: O(n)+O(m)=O(n+m)
• Log base doesn't matter