Time complexity (number of basic operations)

Space complexity (memory usage)

Predicts scalability as data grows

Compares algorithms independent of hardware details

Helps choose trade-offs (speed vs memory, simplicity vs performance)

Number of elements in an array/list

Number of nodes/edges in a graph (V, E)

Digits/bits in a number

Length of a string

Separate variables (e.g., n and m)

Example: scanning matrix n×m → O(nm)

Count dominant primitive steps (comparisons, assignments, arithmetic)

Ignore constant-time implementation details

Interested in how runtime scales as n increases

Asymptotic analysis (behavior for large n)

Best-case

Average-case

Worst-case (often reported for guarantees)

Average cost per operation over a sequence

Example: dynamic array append is amortized O(1)

Big-O gives an asymptotic upper bound on growth

At most grows like a function, up to constant factors

f(n) ∈ O(g(n)) if ∃ constants c > 0, n₀ such that for all n ≥ n₀:

Constant multipliers (e.g., 3n vs n → both O(n))

Lower-order terms (e.g., n² + n + 1 → O(n²))

Quick comparison of scalability

Hardware- and language-independent approximation

Drop constants: O(5n) → O(n)

Keep dominant term: O(n² + n) → O(n²)

Combine sequential parts: O(f(n) + g(n)) → O(max(f(n), g(n)))

Nested loops multiply: O(f(n)) inside O(g(n)) → O(f(n)·g(n))

Log base irrelevant: O(log₂ n) = O(log₁₀ n) = O(log n)

f(n) is both O(g(n)) and Ω(g(n))

Grows at the same rate asymptotically

At least grows like a function

Strictly smaller / strictly greater growth

Array index access, stack push/pop

Binary search

Balanced BST operations (search/insert/delete)

Single pass over an array

Efficient comparison sorts (merge sort, heap sort, quicksort average-case)

Double nested loops over n

Simple sorts (bubble, insertion, selection) worst/average depending

Triple nested loops; naive matrix multiplication variants

Subset enumeration, naive recursion for some problems

Permutation enumeration, brute-force TSP

For large n: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

Extra memory used as n grows

Includes auxiliary data structures and recursion stack

In-place algorithms: O(1) extra space (not counting input)

Merge sort: O(n) extra space (typical implementation)

DFS recursion stack: O(depth) (O(n) worst-case)

Memoization increases space to reduce time

Precomputation and caching

Single loop 1..n → O(n)

Nested loops n×n → O(n²)

Loop halves each time (n, n/2, n/4, …) → O(log n)

Use recurrence relations

Common examples

Hash table average O(1) lookup, worst-case O(n)

Balanced BST O(log n) operations

Identify the largest-growing component as n becomes large

Drop constant and coefficient → O(n)

Dominant term n² → O(n²)

Dominant term n log n → O(n log n)

Constant factor ignored → O(n²)

Combine → O(log n)

Best/average: O(n log n)

Worst-case: O(n²) (poor pivot choices)

Linear search: best O(1), worst O(n)

Binary search (sorted): worst O(log n)

Provides guarantees for performance limits

Real time depends on constants, caching, IO, language overhead

O(n) with huge constant may be slower than O(n log n) for small inputs

Asymptotic comparisons matter most for large n

Distribution of inputs affects expected performance

Security/adversarial inputs can trigger worst cases

Small n: simpler code may be fine

Large n: prefer better asymptotic complexity

Measure real performance for typical workloads

Memory limits, IO costs, parallelism, constant factors

Input distribution, data structure guarantees, hashing behavior