Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Asymptotic notation and the step-count method

Asymptotic notation (O, Ω, Θ, little-o, little-ω) and the step-count method for analyzing algorithm running time and space, with formal definitions, properties, and worked analyses.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

As an engineer, you must compare algorithms independent of machine, compiler, or language. Asymptotic notation gives a standard way to describe growth rates, and the step-count method teaches how to count operations to derive those growth rates. You will use these ideas throughout design and analysis of data structures and algorithms, and to argue performance in reports and interviews.

Key ideas

  • Operation (primitive operation): An elementary action assumed to take constant time under a fixed model (e.g., arithmetic on fixed-size integers, comparison of two integers, assignment, array indexing).
  • Step-count method: A way to estimate an algorithm’s running time by counting how many primitive operations it performs as a function of input size n. We write a function T(n) = number of steps on inputs of size n.
  • Input size (n): A numeric measure of the input, e.g., number of items in an array, number of vertices/edges in a graph, number of bits in a number. State clearly what n denotes before analysis.
  • Cost model assumptions: We assume (unless otherwise stated):
    • Each primitive operation costs a constant unit time.
    • Cost of a loop = number of iterations × cost per iteration.
    • Cost of a conditional = cost of condition evaluation + cost of taken branch.
    • For recursion, define recurrences from the structure of calls + combine costs.
    • We analyze for large n (asymptotic behavior), ignore machine constants.
  • Asymptotic analysis: Studying T(n) as n → ∞, focusing on leading growth and ignoring lower-order terms and constant multiplicative factors.
  • Big-O notation (O): Upper bound growth rate.
    • Definition (formal): For functions f, g: ℕ → ℝ≥0, f(n) ∈ O(g(n)) if ∃ constants c > 0 and n₀ ∈ ℕ such that ∀ n ≥ n₀, f(n) ≤ c·g(n).
    • Meaning: f grows no faster than a constant times g, asymptotically.
  • Big-Ω notation (Ω): Lower bound growth rate.
    • Definition: f(n) ∈ Ω(g(n)) if ∃ constants c > 0 and n₀ ∈ ℕ such that ∀ n ≥ n₀, f(n) ≥ c·g(n).
    • Meaning: f grows at least as fast as a constant times g, asymptotically.
  • Big-Θ notation (Θ): Tight bound growth rate.
    • Definition: f(n) ∈ Θ(g(n)) if ∃ constants c₁, c₂ > 0 and n₀ ∈ ℕ such that ∀ n ≥ n₀, c₁·g(n) ≤ f(n) ≤ c₂·g(n).
    • Equivalently: f ∈ O(g) and f ∈ Ω(g) simultaneously.
  • Little-o notation (o): Strictly smaller growth.
    • Definition: f(n) ∈ o(g(n)) if ∀ c > 0, ∃ n₀ such that ∀ n ≥ n₀, f(n) < c·g(n). Equivalently, limₙ→∞ f(n)/g(n) = 0 (when the limit exists).
  • Little-ω notation (ω): Strictly larger growth.
    • Definition: f(n) ∈ ω(g(n)) if ∀ c > 0, ∃ n₀ such that ∀ n ≥ n₀, f(n) > c·g(n). Equivalently, limₙ→∞ f(n)/g(n) = ∞ (when the limit exists).
  • Nonnegativity assumption: Standard asymptotic definitions assume f(n), g(n) are nonnegative for sufficiently large n. Always state this in formal answers.
  • Best, worst, average case: For a given algorithm, T_best(n), T_worst(n), T_avg(n) are three different functions. Asymptotic notation may be applied to any of them. Explicitly state which one you are analyzing.
  • Dominance of terms: For polynomials, the highest-degree term dominates asymptotically. For logs and exponentials: log n ≪ n^ε (any ε > 0), n^k ≪ c^n (any c > 1).
  • Change of logarithm base: For bases a, b > 1, log_a n = (log_b n) / (log_b a) = constant × log_b n. Hence, asymptotically, the base of log does not matter.
  • Transitivity and properties:
    • If f ∈ O(g) and g ∈ O(h), then f ∈ O(h).
    • If f ∈ Θ(g) and g ∈ Θ(h), then f ∈ Θ(h).
    • If f ∈ O(g), then g ∈ Ω(f). If f ∈ o(g), then g ∈ ω(f).
    • If f ∈ Θ(g), then f ∈ O(g) and f ∈ Ω(g). Conversely, if both hold, then f ∈ Θ(g).
    • If f ∈ O(g) and h ∈ O(g), then f + h ∈ O(g).
    • If f ∈ O(g) and h ∈ O(k), then f·h ∈ O(g·k).
    • For monotone nondecreasing f, ∑_{i=1}^n f(i) ∈ Θ(n·f(n)) if f is polynomially bounded and “smooth” (e.g., f(i) = i^k, log i). Common special cases: ∑ i = Θ(n^2), ∑ i^2 = Θ(n^3), ∑ log i = Θ(n log n).
  • Step-count patterns (how to build T(n)):
    • Sequential composition: T_total(n) = T₁(n) + T₂(n) + …
    • Conditionals: T(n) = cost(test) + max(cost(true-branch), cost(false-branch)) for worst-case; min for best-case; probability-weighted for average-case.
    • Loops:
      • For loop: for i in [1..m(n)]: T_loop(n) = ∑_{i=1}^{m(n)} cost_per_iter(i, n). If cost per iteration is constant c, then T_loop(n) = c·m(n).
      • Nested loops: multiply or sum as per indices. Example: for i=1..n, for j=1..n: total = n·n = n^2 iterations (if inner cost constant).
      • Varying bounds: for i=1..n, for j=1..i: total = ∑_{i=1}^n i = n(n+1)/2 = Θ(n^2).
    • Logarithmic loops: while n > 1: n = ⌊n/2⌋: exactly ⌊log₂ n⌋ iterations (using integer division).
    • Recursion: Write recurrence from subproblems and combining work. Solve by expansion, recursion tree, or Master Theorem (you will study divide and conquer separately; here we use it only to connect step-count to asymptotics).
  • Space complexity (brief context): Similar counting can be applied to memory usage, typically as functions S(n). Asymptotic notation applies the same way.
  • Units: Step counts and complexity classes are dimensionless (no SI unit), but keep explicit constants in intermediate algebra when asked to count operations.

Exact statements commonly examined and their derivations:

  1. Theorem: f ∈ Θ(g) iff f ∈ O(g) and f ∈ Ω(g).
    • Proof sketch: (⇒) Direct from definition with c₁, c₂. (⇐) Use max of thresholds to combine the two inequalities.
  2. Law: Change of base of logarithm: log_a n = (log_b n)/(log_b a).
    • Derivation: Let x = log_a n ⇒ a^x = n. Taking log base b: x·log_b a = log_b n ⇒ x = log_b n / log_b a.
  3. Growth comparisons (for k > 0, ε > 0, c > 1):
    • log n ∈ o(n^ε). Proof by L’Hôpital’s rule or Cauchy condensation; ratio (log n)/(n^ε) → 0.
    • n^k ∈ o(c^n). Ratio test or root test; exponential dominates polynomial.
  4. Summation facts often required:
    • ∑_{i=1}^n i = n(n+1)/2.
    • ∑_{i=1}^n i^2 = n(n+1)(2n+1)/6.
    • ∑_{i=1}^n log i = log(n!). Using Stirling’s approximation (from other courses): log(n!) ∈ Θ(n log n).

Diagram to draw (if asked): “Growth-rate comparison curves”. Instructions:

  • Draw x-axis labeled n (input size), y-axis labeled time (steps).
  • Plot curves in increasing order: log n (lowest), √n, n, n log n, n^2, n^3, 2^n (highest), all starting near the origin. Label each clearly. Mark that base of log is irrelevant asymptotically.

Formulas

f(n) ∈ O(g(n)) ⇔ ∃ c > 0, ∃ n₀, ∀ n ≥ n₀: f(n) ≤ c·g(n) — Asymptotic upper bound; f, g ≥ 0 for large n; dimensionless. f(n) ∈ Ω(g(n)) ⇔ ∃ c > 0, ∃ n₀, ∀ n ≥ n₀: f(n) ≥ c·g(n) — Asymptotic lower bound; f, g ≥ 0 for large n; dimensionless. f(n) ∈ Θ(g(n)) ⇔ ∃ c₁, c₂ > 0, ∃ n₀, ∀ n ≥ n₀: c₁·g(n) ≤ f(n) ≤ c₂·g(n) — Tight bound; f, g ≥ 0 for large n; dimensionless. f(n) ∈ o(g(n)) ⇔ ∀ c > 0, ∃ n₀, ∀ n ≥ n₀: f(n) < c·g(n) — Strictly smaller growth; f, g ≥ 0 for large n; dimensionless. f(n) ∈ ω(g(n)) ⇔ ∀ c > 0, ∃ n₀, ∀ n ≥ n₀: f(n) > c·g(n) — Strictly larger growth; f, g ≥ 0 for large n; dimensionless. log_a n = (log_b n)/(log_b a) — Change of base; a, b > 1; dimensionless. ∑_{i=1}^n i = n(n+1)/2 — Sum of first n integers; n ∈ ℕ. ∑_{i=1}^n i^2 = n(n+1)(2n+1)/6 — Sum of squares; n ∈ ℕ. ∑_{i=1}^n log i = log(n!) — Harmonic-log link; dimensionless; leads to Θ(n log n). T_total(n) = T₁(n) + T₂(n) + … — Sequential composition in step-count method. T_loop(n) = ∑_{i=1}^{m(n)} cost_per_iter(i, n) — Loop step-count; m(n) iterations. T_worst(n) = cost(test) + max(cost(true), cost(false)) — Worst-case selection cost. T_best(n) = cost(test) + min(cost(true), cost(false)) — Best-case selection cost.

Worked examples

Example 1: Step-count and Θ for nested loops with triangular iterations Question: Analyze the number of primitive operations and find the Θ-bound for the following pseudo-code. Assume each assignment, addition, comparison, and array access costs 1 time unit.

for i = 1 to n: for j = 1 to i: s = s + A[j]

Model answer:

  1. Define input size: n = length of array A.
  2. Outer loop runs n times (i = 1..n).
  3. For a fixed i, inner loop runs i times. Each iteration performs:
    • Index A[j]: 1
    • Fetch A[j] and add to s: 1 (add) + 1 (assignment) = 2 Total per inner iteration = 3 operations (constant c = 3). We ignore loop-control overhead (increments and loop-condition checks) because it only affects constant factors in the final Θ(n^2) bound.
  4. Total operations = ∑{i=1}^n (i × 3) = 3 ∑{i=1}^n i = 3·n(n+1)/2 = (3/2) n^2 + (3/2) n.
  5. Therefore T(n) = (3/2) n^2 + (3/2) n ∈ Θ(n^2). Under this body-only cost model, the counted work is (3/2) n^2 + (3/2) n.

Example 2: Best, average, worst case for linear search Question: Using step-count, derive T_best(n), T_avg(n), T_worst(n) for linear search in an array of size n, assuming each comparison costs 1, and assignment/access cost is constant and ignored for simplicity. Assume the key is present with probability 1 and is equally likely to be at any position (for average case under presence).

Algorithm (pseudo-code): for i = 1 to n: if A[i] == key: return i return −1

Model answer:

  1. Define input size: n = number of elements in A.
  2. Worst case: key at position n (or absent). Comparisons: n. So T_worst(n) = n ∈ Θ(n).
  3. Best case: key at position 1. Comparisons: 1. So T_best(n) = 1 ∈ Θ(1).
  4. Average case (key present, uniform position): Expected comparisons = (1 + 2 + … + n)/n = (n+1)/2. So T_avg(n) = (n+1)/2 ∈ Θ(n). If the key might be absent with some probability p, include that in expectation (not required here).

Example 3: Logarithmic loop and recurrence to Θ Question: Consider this code segment and find its Θ-bound by step-count.

count = 0 while n > 0: n = n // 2 for j = 1 to k: count += j

Assume integer division, k is a fixed positive integer constant, and each primitive operation costs 1.

Model answer:

  1. Outer loop: condition n > 0, then n := ⌊n/2⌋. Number of iterations = ⌊log₂ n⌋ + 1 (since each iteration halves n until it reaches 0). Hence outer iterations L ∈ Θ(log n).
  2. Inner loop: for fixed k, iterations = k, work per iteration is constant. Sum of j from 1..k = k(k+1)/2 = constant C (depends on k but independent of n). Step cost per outer iteration is Θ(1) (specifically, about C plus a few fixed assignments/comparisons).
  3. Total work T(n) = L × Θ(1) = Θ(log n). Precisely: T(n) ≈ (⌊log₂ n⌋ + 1) × (k(k+1)/2 + c₀) for some fixed c₀.
  4. Therefore T(n) ∈ Θ(log n).

Optional note (if asked to formalize the logarithm bound): Since n, ⌊n/2⌋, ⌊n/4⌋, … reaches 0 after t steps where 2^t > n ≥ 2^{t−1}, t = ⌊log₂ n⌋ + 1.

Example 4: From step-count to recurrence (divide and conquer flavor, simple) Question: Write a recurrence for T(n) and solve its Θ-bound for the following recursive procedure (n is a power of 2):

procedure F(n): if n == 1: return 1 do a constant amount of work F(n/2); F(n/2)

Model answer:

  1. Step-count: Two recursive calls on size n/2 and constant combination work ⇒ T(n) = 2·T(n/2) + c, with T(1) = d (constants c, d > 0).
  2. Solve by expansion or Master Theorem (reference only): a = 2, b = 2, f(n) = c = Θ(1). Compare n^{log_b a} = n^{log₂ 2} = n^1 = n. Since f(n) = Θ(1), this matches Case 1 of the Master Theorem (because f(n) = O(n^{log_b a − ε}) with ε = 1): T(n) = aT(n/b) + f(n).
    • Here f(n) = Θ(n^k) with k = 0, and n^{log_b a} = n^1. Since k < 1, this is Case 1: f(n) = O(n^{log_b a − ε}) for ε = 1. Hence T(n) ∈ Θ(n).
  3. Therefore T(n) ∈ Θ(n).

Common mistakes

  • Mixing step-count constants with asymptotic classes: writing T(n) = 3n ∈ O(3n) instead of O(n). Constants must be dropped in O, Ω, Θ answers.
  • Using O for exact equality (“T(n) = O(n^2)” as if it were exact). Big-O is an upper bound; a tight bound should be given with Θ when known.
  • Ignoring nonnegativity requirement in formal definitions; always specify “for n large enough, functions are nonnegative”.
  • Treating log base as changing the class (e.g., thinking log₂ n ≠ Θ(log₁₀ n)). They are Θ-equivalent.
  • Incorrect loop counts with triangular or decreasing bounds (e.g., assuming n^2 for nested loops where inner runs only i times; correct is Θ(n^2/2) = Θ(n^2)).
  • Average-case misuse: adding best and worst and dividing by two; correct is expected value weighted by probabilities.
  • For recursion, forgetting base case cost T(1) and applicability conditions (n power of 2, or floor/ceiling handling).
  • Claiming “o” or “ω” without strictness: remember o(g) means strictly smaller (limit ratio 0), not just bounded.

For your exam

  • Precise definitions of O, Ω, Θ, o, ω (with constants and n₀). State nonnegativity and “for all n ≥ n₀”.
  • Prove that f ∈ Θ(g) iff f ∈ O(g) and f ∈ Ω(g).
  • Show that log base change is a constant factor (derive formula).
  • Order the functions by growth: log n, n, n log n, n^2, 2^n, etc., with justification.
  • Short notes:
    • Step-count method: assumptions, how to handle loops, conditionals, recursion.
    • Best/average/worst cases with examples (e.g., linear search).
  • Derivations:
    • Summations for triangular loops: derive ∑ i = n(n+1)/2 and use to get Θ(n^2).
    • Show that ∑ log i ∈ Θ(n log n) (via bounds on log(n!)).
  • Numericals (counting operations):
    • Given small code, compute exact step-count under a stated cost model, then simplify to Θ.
  • Diagrams:
    • Draw and label growth-rate curves and explain their ordering.
  • Recurrence to Θ (light):
    • Derive recurrence from code (e.g., T(n) = 2T(n/2) + c) and state Θ by standard methods; mention Master Theorem by name but do not re-teach it here.

A full-marks answer typically includes: clear definition of n, precise case (best/worst/average), step-by-step counting or inequalities, correct summation, final Θ-class with justification, and, if asked, a neat labeled diagram.

Quick check

  1. State the formal definition of f(n) ∈ O(g(n)). What assumptions on f and g must be mentioned?
  2. For the nested loops: for i = 1..n; for j = 1..i do constant work — what is the total number of iterations and the Θ-bound?
  3. Which grows faster asymptotically: n log n or n^{1.1}? Justify in one line.

Answers: 1) ∃ c > 0, ∃ n₀ such that ∀ n ≥ n₀, f(n) ≤ c·g(n); assume f, g ≥ 0 for large n. 2) Total iterations = ∑_{i=1}^n i = n(n+1)/2; Θ(n^2). 3) n^{1.1} grows faster; since log n ∈ o(n^{0.1}), n log n ∈ o(n^{1.1}).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?