Time Complexity

Time complexity measures how the running time of an algorithm grows as the input size n increases. It focuses on the rate of growth, not exact times.

We measure the worst case (maximum steps for any input of size n) unless specified otherwise.

Big-O Notation

Big-O notation is a mathematical notation that describes the upper bound of an algorithm's time complexity — how many operations it performs as a function of input size n in the worst case.

• Constants and lower-order terms are dropped (we care about growth rate only)
• E.g. 3n² + 5n + 2 → O(n²)

Common Time Complexities

Growth rate comparison (small n)

n=10:   O(1)=1, O(log n)≈3, O(n)=10, O(n log n)≈33, O(n²)=100, O(2ⁿ)=1024
n=100:  O(1)=1, O(log n)≈7, O(n)=100, O(n log n)≈664, O(n²)=10000, O(2ⁿ)=huge!

Order from most to least efficient: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

Identifying Complexity from Code

// O(1) — constant time
x = arr[5]

// O(n) — single loop
for i in range(n):
    print(arr[i])

// O(n²) — nested loops
for i in range(n):
    for j in range(n):
        print(arr[i], arr[j])

// O(log n) — halving each iteration
left, right = 0, n-1
while left <= right:
    mid = (left + right) // 2
    if arr[mid] == target: return mid
    elif arr[mid] < target: left = mid + 1
    else: right = mid - 1

Space Complexity

Space complexity measures memory usage as n grows, using the same Big-O notation.