Time complexity (number of basic operations)

Space complexity (extra memory used)

Number of elements in an array/list

Number of nodes/edges in a graph (n, m)

Number of digits/bits in a number

Length of a string

Clearly define n for the problem to avoid misleading complexity claims

Maximum cost over all inputs of size n

Most common in guarantees and Big-O discussions

Expected cost under an assumed input distribution

Useful but depends on realistic assumptions

Minimum cost over inputs of size n

Often less informative unless it occurs frequently

Average cost per operation over a sequence (e.g., dynamic array append)

Smooths occasional expensive operations

Describes an asymptotic upper bound on growth rate as n becomes large

Focuses on how runtime/space scales, not exact counts

f(n) ∈ O(g(n)) if there exist constants c > 0 and n₀ such that

Ignore constant factors (×10) and lower-order terms (+ n) for large n

Keep the dominant term that grows fastest as n increases

Drop constants

Drop lower-order terms

Sequential steps add

Nested loops multiply

Conditionals take the worst branch (for worst-case analysis)

Logarithms: base doesn’t matter in Big-O

Big-O (O): upper bound (at most)

Big-Ω (Ω): lower bound (at least)

Big-Θ (Θ): tight bound (both upper and lower; “exact” asymptotic class)

Big-O is not inherently “worst-case,” but it’s frequently used to express worst-case bounds

Always clarify the case (worst/average/best/amortized)

Array index access

Push/pop on stack (typical)

Binary search in a sorted array

Operations on balanced BSTs (search/insert/delete)

Single pass through an array (sum, max)

Linear search

Efficient comparison-based sorting (merge sort, heapsort, average quicksort)

Many divide-and-conquer algorithms

Double nested loops over n items

Simple sorts (bubble, selection, insertion worst-case)

Triple nested loops (basic matrix multiplication)

Brute-force subsets, naive Fibonacci recursion

Brute-force permutations (traveling salesman naive)

Big-O describes growth, but constant factors still matter for moderate n

Cache behavior, language overhead, and I/O can dominate

Comparisons in sorting/searching

Arithmetic operations

Pointer/array accesses

Single loop over n → O(n)

Nested loop i=1..n, j=1..n → O(n²)

Nested loop i=1..n, j=1..i → O(n²) (about n(n+1)/2)

Divide-and-conquer halves input each step → O(log n) levels

Auxiliary space: extra memory beyond input storage

Total space: input + auxiliary

In-place algorithms: O(1) auxiliary space (e.g., heapsort)

Recursion stack

Data structures

Access by index: O(1)

Search unsorted: O(n)

Insert/delete in middle: O(n) due to shifting

Insert/delete at known node/head: O(1)

Search: O(n)

Random access: O(n)

Insert/search/delete: O(1) average, O(n) worst (collisions/adversarial)

Insert/search/delete: O(log n)

Find min/max: O(1)

Insert: O(log n)

Extract min/max: O(log n)

Build heap: O(n)

O(1) stays flat

O(log n) grows slowly

O(n) grows proportionally

O(n log n) grows faster than linear but much slower than quadratic

O(n²), O(n³) quickly become impractical

O(2ⁿ), O(n!) explode rapidly even for modest n

For huge n or big constants, it can still be slow

Saying an algorithm is O(n²) can be true even if it is Θ(n)

Prefer Θ when you know a tight bound

Quicksort average O(n log n), worst O(n²)

Hash tables average O(1), worst O(n)

Graph algorithms often use O(n + m) rather than O(n²)

Matrix operations can be expressed in terms of rows and columns

Big-O is asymptotic; real runtime includes constants and lower-order terms

For i in 1..n do constant work → O(n)

Loop n + loop n → O(n + n) = O(n)

For i in 1..n

Each step halves the search space → O(log n)

Split into halves (log n levels) + merge costs O(n) each level → O(n log n)