Big O — Understanding Performance

Big O notation describes how an algorithm's runtime scales with input size.

Common complexities:

O(1) — Constant: Dict lookup, list append, set membership. Same speed regardless of size.

O(log n) — Logarithmic: Binary search. Doubles input, adds one step.

O(n) — Linear: Loop through list. 10x input = 10x time.

O(n log n) — Linearithmic: Python's sort (Timsort). Efficient for sorting.

O(n²) — Quadratic: Nested loops. 10x input = 100x time.

O(2^n) — Exponential: Naive fibonacci. Avoid for large inputs.

Python examples:

x in my_list    # O(n) — scans entire list
x in my_set     # O(1) — hash lookup
my_list.sort()  # O(n log n)
my_list[i]      # O(1) — direct index
my_list.insert(0, x)  # O(n) — shifts all elements

Rule of thumb: If n > 10,000, O(n²) is too slow. Use better algorithms or data structures.

Reference:

Wikipedia: Big O Notation

https://en.wikipedia.org/wiki/Big_O_notation