Time Complexity & Asymptotic Analysis

Time complexity measures how the runtime of an algorithm grows as the input size increases. We use asymptotic notation to express this growth in a hardware-independent way. Understanding complexity lets you choose the right algorithm for large datasets.

Big-O Notation (Upper Bound)

Big-O describes the worst-case growth rate. f(n) = O(g(n)) means that for sufficiently large n, f(n) is bounded above by a constant multiple of g(n).

Common Big-O Classes

# O(1) — constant time
def get_first(arr):
    return arr[0]

# O(n) — linear time
def linear_search(arr, target):
    for i, v in enumerate(arr):
        if v == target:
            return i
    return -1

# O(n^2) — quadratic time
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

# O(log n) — logarithmic time
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Omega Notation & Theta Notation

• Ω (Omega) — Lower bound. f(n) = Ω(g(n)) means f(n) grows at least as fast as g(n). Describes the best-case scenario.
• Θ (Theta) — Tight bound. f(n) = Θ(g(n)) means f(n) grows exactly as fast as g(n) (both upper and lower bound match). This is the most precise characterization.

Analyzing Loops and Recursion

Single Loop

A loop that runs n times is O(n). If the loop variable halves each time (e.g., while i > 0: i //= 2), it is O(log n).

Nested Loops

Two nested loops each running n times yield O(n²). A loop of n iterations with an inner loop that runs i times yields O(n²) as well (sum of 1 to n is n(n+1)/2).

Recurrence Relations

Recursive algorithms are analyzed using recurrences. For mergesort: T(n) = 2T(n/2) + O(n), which solves to T(n) = O(n log n) via the Master Theorem.

# Fibonacci: O(2^n) naive vs O(n) with DP
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

def fib_dp(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Complexity of Sorting Algorithms

Complexity of Searching Algorithms

Space Complexity

Space complexity measures the amount of extra memory an algorithm uses. An in-place algorithm uses O(1) extra space (e.g., Bubble Sort). Algorithms that allocate new arrays (e.g., Merge Sort) use O(n) extra space. Recursion adds call stack space — a recursive function that calls itself n times deep uses O(n) stack space.

# Snippet 1
for i in range(n):
    for j in range(i, n):
        print(i, j)

# Snippet 2
i = n
while i > 0:
    print(i)
    i //= 2

# Snippet 3
for i in range(n):
    for j in range(10):
        print(i, j)

# Snippet 4
def mystery(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = mystery(arr[:mid])
    right = mystery(arr[mid:])
    return merge(left, right)