Big O (O) = upper bound (worst case will not exceed this)
Big Omega (Ω) = lower bound (best case will be at least this)
Big Theta (Θ) = tight bound (O and Ω both equal this)
We often say "O(n)" when we really mean "Θ(n)" but Big O is the convention even when it's technically an upper bound.

Big O describes scaling behavior, not absolute time. A 10n operation and a 0.1n operation both scale linearly—doubling n doubles the time for both. The constant depends on hardware, compiler, and implementation details. Stripping constants lets us compare fundamental algorithmic efficiency independent of implementation details. We assume any constant factor can be "good enough" hardware to make the analysis meaningful.

It means the runtime grows proportionally to n × log(n). For n=1000, that's 1000 × 10 ≈ 10,000 operations. This is better than O(n²) which would be 1,000,000 operations, but worse than O(n) which would be 1,000. Merge sort achieves O(n log n); it's optimal for comparison-based sorting (proved via information-theoretic lower bound).

Amortized analysis guarantees the average performance of each operation over a worst-case sequence of operations. It spreads the cost of expensive operations across many cheap ones. Average-case analysis assumes a probabilistic distribution of inputs and computes the expected cost. The key difference: amortized makes no probabilistic assumptions — it bounds the total cost of any sequence of n operations divided by n. Example: dynamic array insertion is O(1) amortized because occasional O(n) resizes are spread across all O(1) insertions.

Use recurrence relations and solve them with the Master Theorem or the substitution method. Steps:

• Write the recurrence: T(n) = aT(n/b) + f(n) where a = number of subproblems, n/b = size of each subproblem, f(n) = cost to divide and combine
• Apply the Master Theorem when f(n) is a polynomial — three cases based on comparing f(n) with n^(log_b a)
• Example: Merge sort recurrence T(n) = 2T(n/2) + O(n) solves to O(n log n) (Case 2 of Master Theorem)
• Fibonacci (naive): T(n) = T(n-1) + T(n-2) + O(1) solves to O(2^n) — two subproblems of nearly the same size

Binary search is O(log n). Each iteration halves the search space: after k iterations, the search space shrinks from n to n/2^k. The algorithm terminates when the search space reaches size 1, giving n/2^k = 1 → 2^k = n → k = log_2(n). This logarithmic halving is optimal for comparison-based search on sorted arrays (information-theoretic lower bound of Ω(log n) comparisons).

Mergesort requires O(n) auxiliary space because merging needs a temporary array of size n. Quicksort is in-place with O(log n) space for the call stack (due to recursion depth). However, quicksort's worst-case space degrades to O(n) when partitioning creates highly unbalanced subproblems — mitigated by using the median-of-three pivot selection. The trade-off: mergesort uses more memory but guarantees O(n log n) time; quicksort is more memory-efficient but has a worst-case O(n²) time that is rare in practice.

The classic example is naive recursive Fibonacci: fib(n) = fib(n-1) + fib(n-2). Each call branches into two, creating an exponential call tree with ~2^n calls. Optimizations:

• Memoization (top-down DP) — cache computed results, reducing to O(n) time and O(n) space
• Iteration (bottom-up DP) — compute iteratively with O(n) time and O(1) space
• Matrix exponentiation — O(log n) time using the closed-form matrix representation

The general principle: exponential algorithms often hide overlapping subproblems that dynamic programming can exploit to achieve polynomial time.

Sum the number of iterations mathematically. For example:

• for i in range(n): for j in range(i): → sum_{i=0}^{n-1} i = n(n-1)/2 = O(n²)
• for i in range(n): for j in range(n, i, -1): → same O(n²) behavior
• for i in range(n): for j in range(i, 0, j//2): → O(n log n) because the inner loop halves each time

The key is to model the inner loop count as a function of the outer variable and compute the summation or use integral approximation.

For a well-distributed hash table with good hash function and load factor management:

• Insert: O(1) average / amortized, O(n) worst case (hash collision clustering)
• Lookup: O(1) average, O(n) worst case (all keys hash to same bucket)
• Delete: O(1) average, O(n) worst case

Important caveats: Hash table performance depends on the hash function quality, load factor, and collision resolution strategy (chaining vs open addressing). Worst-case O(n) occurs when every key collides — a realistic concern under algorithmic complexity attacks if hash functions are predictable.

The Master Theorem solves recurrence relations of the form: T(n) = aT(n/b) + f(n) where a ≥ 1 and b > 1. It gives asymptotic bounds for three cases:

• Case 1: If f(n) = O(n^(log_b a - ε)) for some ε > 0, then T(n) = Θ(n^(log_b a))
• Case 2: If f(n) = Θ(n^(log_b a) * log^k n) for k ≥ 0, then T(n) = Θ(n^(log_b a) * log^(k+1) n)
• Case 3: If f(n) = Ω(n^(log_b a + ε)) for some ε > 0, and f(n) satisfies the regularity condition, then T(n) = Θ(f(n))

Example: Merge sort T(n) = 2T(n/2) + O(n) gives a=2, b=2, log_b a = 1. Since f(n) = Θ(n^1), it matches Case 2 with k=0, yielding T(n) = Θ(n log n).

Space complexity of recursion includes the call stack depth multiplied by the space per frame:

• Recursion depth = how many nested calls active at once
• Per-frame space = local variables, parameters, return address
• Example: Binary search recursion depth is O(log n) → space O(log n)
• Example: Naive Fibonacci recursion depth is O(n) but tree breadth makes total space O(n) — each level has two active calls

Memoization reduces repeated subproblem storage but can increase space usage if the cache grows larger than the call stack would have been. The trade-off depends on whether time or space is the tighter constraint.

Time complexity measures operations as input grows; space complexity measures memory usage as input grows. They don't always trade off:

• Bubble sort: Time O(n²), Space O(1) — slow but memory-efficient
• Mergesort: Time O(n log n), Space O(n) — faster but needs auxiliary array
• Depth-first search: Time O(V+E), Space O(V) for visited set + recursion stack
• BFS: Time O(V+E), Space O(V) for queue — same time, similar space

Trade-offs exist: quicksort is in-place O(log n) space but O(n²) worst-case time; mergesort guarantees O(n log n) time but needs O(n) space. Choosing between them requires understanding which resource is constrained.

These describe how algorithm performance varies with different input distributions:

• Best case: The most favorable input for the algorithm. Example: O(1) for quicksort if pivot always lands in the middle.
• Average case: Expected performance over all possible inputs (assumes some distribution, often uniform random). Example: O(n log n) for quicksort with random pivots.
• Worst case: The most unfavorable input. Example: O(n²) for quicksort when pivot is always the smallest or largest element.

When someone says "O(n)" without qualification, they usually mean worst-case. Best case is rarely useful for analysis; average case requires probabilistic assumptions that may not hold in production. Worst case gives a guaranteed upper bound and is the standard for rigorous analysis.

When an algorithm's complexity depends on multiple independent parameters, you must keep all variables in the notation:

• O(n + m) — two independent variables, both affect runtime
• O(n × m) — nested loops over two different-sized inputs
• O(n² + m) — quadratic in n plus linear in m

Common mistake: dropping m when it represents a different scaling factor than n. If your input is a list of n records and each record has m fields, and you iterate over all fields, that's O(n × m) — you cannot say O(n) because m matters for practical runtime.

For graph algorithms with V vertices and E edges: O(V + E) for DFS/BFS, O(V²) for dense graphs using adjacency matrix, O(V × E) for Bellman-Ford.

A recurrence relation expresses algorithmic complexity as a function of smaller inputs. Solving it gives you a closed-form expression for total cost:

• Substitution method: Guess a form and prove by induction. Example: T(n) = 2T(n/2) + n. Guess T(n) = O(n log n), verify.
• Master Theorem: Apply when T(n) = aT(n/b) + f(n) with a ≥ 1, b > 1.
• Recursion trees: Expand the recurrence, sum the cost at each level. Useful for seeing the pattern before applying Master Theorem.

Example: T(n) = 3T(n/2) + n. Here a=3, b=2, n^(log_b a) = n^(log_2 3) ≈ n^1.585. Since f(n) = n = O(n^1.585 - ε), Case 1 applies: T(n) = Θ(n^(log_2 3)) ≈ Θ(n^1.585).

Selection sort is O(n²) — slower than O(n log n) algorithms for large inputs. However, it has properties that make it preferable in specific scenarios:

• Memory constrained: Selection sort is in-place O(1) space, vs O(n) for mergesort or O(log n) recursion for quicksort.
• Write-heavy environments: Selection sort makes at most n swaps (exchanges), vs many more in bubble sort variants. Useful when writing to memory is expensive (e.g., EEPROM with limited write cycles).
• Nearly sorted data: Selection sort doesn't improve on nearly sorted data, but it never degrades further — always O(n²).
• Small arrays: For very small n (say n < 10), the constant factors of O(n log n) sort algorithms can dominate, making selection sort faster in practice.

In general, for n > 50 or so, O(n log n) algorithms win. But the specific constraints of your environment determine which is right.

Big O notation ignores memory hierarchy effects. In practice, cache performance can dominate runtime even when asymptotic complexity suggests otherwise:

• Cache lines: CPUs fetch data in chunks (64 bytes typically). Accessing contiguous memory loads the entire line — fast. Strided access (jumping every n elements) causes cache misses.
• Row vs column access: Iterating rows then columns in a 2D array keeps data in cache. Iterating columns then rows causes a cache miss per row, making the same O(n²) operation 10-100x slower.
• Merge sort vs quicksort: Mergesort does sequential scans and good cache utilization, but requires O(n) auxiliary space. Quicksort has poor cache locality on the recursion stack but is in-place.
• Hash tables: O(1) expected, but poor hash function causes clustering and cache line inefficiencies that degrade practical performance below theoretical O(1).

For small inputs, cache effects can outweigh asymptotic benefits. For large datasets, asymptotic efficiency usually dominates — but only if the implementation respects memory access patterns.

Big O (asymptotic upper bound) means f(n) = O(g(n)) if there exist constants c and n₀ such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀. It gives a ceiling that may or may not be tight.

Little o (asymptotically strictly smaller) means f(n) = o(g(n)) if for all c > 0, there exists n₀ such that 0 ≤ f(n) < c·g(n) for all n ≥ n₀. It means f(n) grows strictly slower than g(n).

• n² = O(n²) and n² = o(n³) — n² is bounded above by n³ but grows strictly slower
• n² ≠ o(n²) — n² does not grow strictly slower than itself
• n log n = o(n²) but n² ≠ o(n log n)

In practice, big O is used for algorithm bounds. Little o appears more in mathematical proofs showing that one algorithm is asymptotically strictly better than another.

This requires understanding the relationship between the termination condition and input characteristics:

• Binary search variant: Searching for a threshold value where f(mid) crosses from false to true. Same O(log n) — halving search space each iteration regardless of where it terminates.
• Skipping duplicates: In sorted array with many duplicates, early termination changes nothing — still O(log n) worst case.
• Linear search with early exit: Finding first match in unsorted array — best case O(1), worst case O(n), average case O(n/2). This is where best/worst case distinction matters.
• Iterative refinement: Algorithms like Newton's method converge at rate depending on numeric properties — may be O(log n) iterations to reach precision, but each iteration costs O(n). Total O(n log n) or more depending on the problem.

Key is identifying the variable that controls loop count and expressing iterations as a function of input size and problem parameters. Often requires domain knowledge about the data distribution.