Chapter 9 — Complexity and Big O notation

What we mean by algorithmic complexity
This topic explains the purpose of analysing algorithms. Algorithmic complexity is about measuring how resources—mainly time and memory—grow as the input size increases. Instead of measuring exact running time in seconds, which depends on the machine and programming language, we describe growth using functions of n, the input size. This abstract view helps compare algorithms independent of implementation details.

Inputs, operations and models
To study time complexity we pick a model of computation where basic operations (assignments, comparisons, arithmetic) take constant time. Input size n should be defined clearly: number of elements in an array, number of bits in a number, number of vertices in a graph, etc. For space complexity, count additional memory required excluding space for input unless stated otherwise.

Counting basic operations
Start by identifying the fundamental operation for the problem — for search it may be a comparison, for arithmetic it may be an addition. Count how many times that operation executes as a function of n. For loops, multiply iterations by work per iteration; for nested loops add up the contributions precisely when needed, or use dominant-term reasoning for asymptotic results.

Why this matters
When n is small, many algorithms perform well. For large n, algorithms with lower growth rates (for example, linear instead of quadratic) can be the difference between feasible and infeasible solutions. Complexity analysis helps software engineers predict scalability, choose data structures, and meet performance requirements.

Practical approach
When learning, practise on simple code fragments: single loops, nested loops, recursive functions. Translate each into an operation count, simplify by keeping the highest-order term and dropping constants, and express the result using asymptotic notation. Always state assumptions: what n is, which operations count as unit cost, and whether you measure worst-case, average-case or best-case.

Formal definition and intuition
Big O notation captures an upper bound on the growth of a function. We write f(n) = O(g(n)) to mean there exist positive constants c and n0 such that for every n ≥ n0, f(n) ≤ c·g(n). Intuitively, beyond some threshold n0, f(n) is no larger than a constant multiple of g(n). This is useful to express worst-case running time up to constant factors and ignoring smaller terms.

Choosing g(n)
When you analyse an algorithm, choose g(n) to be a simple function that reflects the dominant growth: common choices are 1, log n, n, n log n, n^2, 2^n and so on. The goal is not to find the tightest possible g(n) for every exercise but to express complexity in a class that shows how the algorithm scales. If asked for a tight bound, provide Θ instead.

Proving Big O claims
To prove f(n) = O(g(n)) using the formal definition, explicitly give values for c and n0 and show the inequality holds. For polynomial expressions, you can often bound lower-degree terms by the leading term when n is large. For example, f(n)=3n^2+5n+20 ≤ 3n^2+5n^2+20n^2 = 28n^2 for n ≥ 1, so choose c=28 and n0=1. State these choices in answers to be clear and rigorous.

Common proof techniques
Use simple inequalities like n ≤ n^2 for n ≥ 1, or log n ≤ n for n ≥ 2. For products like n log n, factor n and use properties of logarithms. When comparing functions whose forms are not immediately obvious, use limits: if lim_{n→∞} f(n)/g(n) = L where L is finite, then f(n)=O(g(n)).

Practical examples and warnings
Examples: 7n+10 = O(n); log n = O(n); n = O(n log n) but not vice versa. Beware of incorrect statements like 2^n = O(n^k) for fixed k — exponentials dominate polynomials. When writing solutions, always indicate the assumed domain (usually integers n ≥ 1) and give the constants used for the formal definition to earn full marks in examinations.

Big Omega explained
Big Omega notation provides a lower bound on growth. Writing f(n) = Ω(g(n)) means that for sufficiently large n, f(n) is at least a constant multiple of g(n). Formally, there exist positive constants c and n0 such that for every n ≥ n0, f(n) ≥ c·g(n). This notation is used to state that the algorithm must use at least that much resource on inputs of size n, often representing best-case behaviour or guaranteed cost.

Big Theta explained
Big Theta is used when we can bound a function both above and below by the same simple function, up to constants. f(n) = Θ(g(n)) means there exist positive constants c1, c2 and n0 such that c1·g(n) ≤ f(n) ≤ c2·g(n) for all n ≥ n0. Θ gives a tight asymptotic characterisation: g(n) captures the growth rate of f(n) within constant factors.

Why both notations matter
O alone gives an upper bound but may be loose; Ω alone gives a lower bound but might be weak. Θ is strongest as it says the two functions are of the same order. When analysing algorithms, Θ is preferred if achievable because it gives precise asymptotic growth. For algorithm descriptions, O is common to state worst-case guarantees, while Ω is used for best-case results.

Techniques to prove Ω and Θ
To show Ω, find c and n0 such that f(n) ≥ c·g(n) holds. Often choose c as the leading coefficient divided by two and pick n0 so lower-order terms are controlled. For Θ, prove both O and Ω separately. Limit comparisons can help: if lim_{n→∞} f(n)/g(n) = L where 0 < L < ∞, then f(n) = Θ(g(n)).

Examples, interpretation and exam tips
3n+4 = Θ(n) since it is both O(n) and Ω(n). Summing an array always does Θ(n) work. Searching an unordered list has best-case Ω(1) if found immediately and worst-case O(n) if not found; therefore you can state both bounds but not Θ(n) without specifying average-case. In exams, explicitly give constants and n0 for formal proofs and explain the meaning of the bound in terms of best/worst/guaranteed behaviour.

Overview and why classes are used
Complexity classes let us group algorithms by growth behaviour so we can compare and choose among them. Students should memorise and understand the practical meaning of common classes: O(1) (constant), O(log n) (logarithmic), O(n) (linear), O(n log n) (linearithmic), O(n^2) (quadratic), O(n^k) (polynomial), and O(2^n) / O(n!) (exponential/factorial). Knowing where an algorithm falls quickly shows whether it can handle large inputs.

Constant time O(1)
Constant-time operations do the same amount of work regardless of n. Examples include accessing an array cell by index, returning a fixed value, or computing a simple arithmetic expression. In code, statements outside loops or fixed-number operations are constant.

Logarithmic O(log n)
Logarithmic time appears when each step reduces the problem multiplicatively. Binary search halves the range each comparison and needs roughly log_2 n comparisons. Balanced search trees and many heap operations have logarithmic time because they move along tree height that grows logarithmically with n.

Linear and linearithmic
Linear algorithms perform work proportional to n, such as a single pass over an array. Linearithmic O(n log n) commonly arises in efficient sorting algorithms: the algorithm performs log n levels of division and does linear work at each level, resulting in n log n total cost. Examples include mergesort and heapsort.

Quadratic and polynomial
Nested loops typically produce polynomial times. Two nested loops give O(n^2), three nested loops O(n^3), and so on. These are acceptable for small n but quickly become costly. Many naive algorithms for pairwise comparisons or matrix operations fall in this category.

Exponential and practical limits
Exponential time, like O(2^n), grows extremely fast and becomes unusable for moderate n. Brute-force search over subsets or permutations often leads to exponential or factorial time. Such algorithms are studied for small n or as theoretical baselines; practical solutions require heuristics, approximation, or special structure to avoid exponential blow-up.

Guidance
Prefer lower asymptotic classes for large-scale problems, but consider constants, memory and implementation complexity. For small inputs, a simpler higher-class algorithm with a tiny constant may be acceptable. Always justify choices based on both asymptotic and practical considerations.

Start with the basic operation
When analysing loops pick a basic operation to count: a comparison, assignment, swap, arithmetic step, or function call. The choice depends on the algorithm. Make it explicit in your solution. The total time is the number of times this operation executes as a function of n, multiplied by the assumed unit cost for each operation.

Single loops
For a simple loop that runs from 1 to n performing constant work, the total cost is c·n for some constant c. In asymptotic terms, this is Θ(n). If the loop bounds are functions of n (like from 1 to 2n), adjust counts accordingly; e.g., 2n iterations are still Θ(n).

Nested loops and sums
For nested loops multiply the iteration counts when inner and outer bounds are independent: two loops each from 1 to n produce n^2 iterations. When inner loop depends on outer variable, convert to a sum — for example nested loops where inner runs up to i produce Σ_{i=1}^n i = n(n+1)/2 = Θ(n^2). Use known closed forms for arithmetic and geometric series to simplify counts precisely when required.

Triangular and irregular patterns
Triangular patterns arise often in algorithms comparing pairs: sum of 1 to n gives Θ(n^2). For loops with varying increments consider their nature: arithmetic increment by constant yields Θ(n) iterations, multiplicative increments (i*=2) yield Θ(log n) iterations. For two-level variable bounds, carefully set up double sums or change the order of summation if that simplifies evaluation.

Multiple sequential pieces
If code has several segments executed in sequence, add their costs. The overall asymptotic complexity is determined by the dominant term. For example, a Θ(n^2) block followed by Θ(n) results in Θ(n^2) overall. Make this explicit so examiners see your reasoning for dropping lower-order terms and constants.

Edge cases and exact counts
When asked for exact operation counts provide the sum expression and its closed form before simplifying to Θ. For example, for the nested loop with inner limit i, show Σ_{i=1}^n i = n(n+1)/2, then state Θ(n^2). Showing both exact and asymptotic forms earns full credit in formal answers.

Logarithm concepts
Understand that log_b n is the exponent to which base b must be raised to obtain n. In complexity, the base b is not important because logs with different fixed bases differ only by a constant factor: log_a n = log_b n / log_b a. Asymptotic notation ignores constant factors, so any logarithm is Θ(log n) regardless of base. Logarithms appear when problem size is reduced multiplicatively each step.

Binary search mechanics
Binary search is the classic logarithmic-time algorithm. Given a sorted array of size n, we compare the target with the middle element and discard half the array each time. The number of steps k needed satisfies 2^k ≥ n, so k = ⌈log_2 n⌉. Therefore binary search runs in Θ(log n) time. Be careful about off-by-one details in implementation, but asymptotic cost remains logarithmic.

Other logarithmic examples
Balanced binary search trees (AVL, red-black) keep height proportional to log n, so operations like search, insert and delete take Θ(log n) time. Heap operations like insertion or extract-min also traverse tree height Θ(log n). Loops that double or halve an index (i*=2 or i/=2) run in Θ(log n) iterations.

Why logarithmic factors matter
Logarithmic-time algorithms scale very well. For example, for n = 1,000,000, log_2 n ≈ 20, which means dramatic speed compared to linear scans. When designing systems for large data sets, replacing linear-time operations with logarithmic ones can produce large practical improvements, even if constants differ.

Combinations with other terms
Often complexity includes logarithmic factors like n log n for sorting or n + log n for combined operations. Interpret such combinations: n log n means doing Θ(log n) work for each of n items (as in mergesort where there are log n levels each costing Θ(n)). In practice, check whether constants or smaller terms matter for the actual input sizes encountered.

Where recurrences come from
Recurrences model running time of recursive algorithms by expressing T(n) in terms of T on smaller inputs. A typical divide-and-conquer recurrence is T(n) = a·T(n/b) + f(n) where the problem is split into a subproblems each of size n/b and f(n) is the cost to divide and combine. Understanding how to solve such recurrences is essential to analysing recursive algorithms.

Methods to solve recurrences
Three common methods are substitution, recursion tree and Master Theorem. Substitution involves guessing a solution form and proving it by induction. The recursion-tree method visualises costs at each level: draw the tree of recursive calls, label node costs, sum costs across levels and determine which level dominates. The Master Theorem provides direct answers for many standard recurrences of the form aT(n/b)+f(n).

Recursion-tree detailed use
Build the tree: root has cost f(n), level 1 has a nodes each cost f(n/b), level 2 has a^2 nodes with cost f(n/b^2), and so on down to leaves of size ~1. Number of levels is about log_b n. Sum cost per level and then sum across levels. Compare total cost of internal nodes and total cost at leaves to see which part dominates asymptotically.

Examples with explanation
Mergesort: a=2, b=2, f(n)=Θ(n). Recursion tree shows each of log n levels contributes Θ(n) so total Θ(n log n). Binary search: T(n)=T(n/2)+Θ(1) has constant per level and log n levels → Θ(log n). For T(n)=T(n-1)+Θ(1) the tree is a path of length n with constant cost per level → Θ(n).

Irregular recurrences and practical tips
Some recurrences are not balanced or have non-polynomial f(n); Master Theorem may not apply. In such cases use substitution or adapt the recursion-tree carefully. When writing exam answers, state base cases, assumptions (such as n power of b if needed), and show either a clear induction proof or a level-wise sum from the recursion tree to reach the final Θ bound.

Why the Master Theorem is useful
The Master Theorem provides a quick mechanical way to solve a wide class of divide-and-conquer recurrences of the form T(n) = a·T(n/b) + f(n) with constants a ≥ 1 and b > 1. It compares the non-recursive cost f(n) with the function n^{log_b a} representing work at the leaves and gives one of three cases to determine Θ(T(n)). Using it saves time and gives clear answers for common algorithms.

The three cases in practical terms
Let k = log_b a. Case 1: If f(n) grows polynomially slower than n^k, i.e., f(n) = O(n^{k-ε}) for some ε > 0, then the leaf cost dominates and T(n) = Θ(n^k). Case 2: If f(n) = Θ(n^k), costs at all levels are balanced and T(n) = Θ(n^k log n). Case 3: If f(n) grows polynomially faster than n^k, i.e., f(n) = Ω(n^{k+ε}) and satisfies a regularity condition a·f(n/b) ≤ c·f(n) for some c < 1, then root cost dominates and T(n) = Θ(f(n)).

Applying the theorem step by step
To apply: identify a and b, compute k = log_b a and compare f(n) with n^k. Use exponent comparison or limit tests. If f(n) matches Case 3 you must also check the regularity condition; state it and verify it holds. If Master Theorem does not fit (unequal subproblem sizes, non-polynomial f(n), etc.) switch to recursion-tree or substitution.

Worked examples and explanation
Mergesort: a=2, b=2 so k=1 and f(n)=n ⇒ Case 2 ⇒ T(n)=Θ(n log n). For T(n)=3T(n/4)+n, compute k=log_4 3 ≈0.79; since f(n)=n grows faster than n^{0.79} we use Case 3 and get T(n)=Θ(n) provided regularity holds (it does). For T(n)=4T(n/2)+n, k=2 and f(n)=n is smaller (Case 1), so T(n)=Θ(n^2).

Limitations and exam advice
Master Theorem does not apply when subproblems are of unequal size or when f(n) involves extra logarithmic factors that change case boundaries. In exam answers, always show identification of a and b, compute k explicitly, state which case applies and show any required regularity verification for Case 3. If the theorem does not apply, state the reason and use substitution or recursion-tree instead.

What amortised analysis means
Amortised analysis finds the average cost per operation over a worst-case sequence of operations, giving a guaranteed bound on amortised cost. It differs from average-case analysis: amortised deals with deterministic worst-case sequences averaged across many operations, while average-case assumes a distribution over inputs. Amortised analysis is useful for data structures that have occasional expensive operations balanced by many cheap ones.

Three methods explained
The aggregate method computes the total cost of a sequence of n operations and divides by n to get the amortised cost per operation. The accounting method assigns an amortised charge to each operation, storing excess as credits to pay for future expensive operations; choose charges so the credit never goes negative. The potential method uses a potential function mapping states to stored energy; the amortised cost equals actual cost plus change in potential and this yields tight bounds for many structures.

Dynamic array in detail
Consider an array that doubles capacity when full. Most append operations cost O(1) to place an element. On resize, copying k elements costs O(k). Resizes happen at sizes 1,2,4,8,...; the total cost of all copies during n appends is less than 2n. Using aggregate method total cost ≤ cn for some constant c, so amortised cost per append is O(1). Accounting method explains this by charging each append 3 units: 1 pays for insertion and 2 saved to pay future copies; show credits always suffice.

Binary counter example
A binary counter increments by flipping bits; sometimes many bits flip (e.g., from 0111 to 1000), but these expensive increments are rare. Over 2^k increments total bit flips are bounded by about 2^{k+1}-1, so amortised flips per increment is constant: O(1). Use accounting or potential methods to formalise this by charging 2 credits per increment to pay for future flips.

Why amortised is important
Amortised analysis shows that data structures with occasional heavy operations still provide efficient guarantees over time. Examples include dynamic arrays, splay trees, queues implemented with two stacks, and hash tables that resize. In exams, clearly state the amortised analysis method used and show arithmetic or bookkeeping to justify the claimed bound.

Definitions and differences
Best-case analysis examines the least amount of work an algorithm can do on any input of size n; worst-case examines the most; average-case gives the expected work assuming a probability distribution over inputs. Worst-case is used when guarantees are required; average-case is useful when inputs follow a known or reasonable distribution. Best-case is rarely used alone to judge an algorithm's usefulness.

How to compute average-case
Average-case complexity is the expected cost: sum_{inputs} cost(input) × P(input). For simple examples assume uniform distribution over positions or permutations, but always state that assumption. Average-case may require combinatorial counting; for linear search with uniform target position average comparisons = (n+1)/2, which is Θ(n).

Examples showing differences
Linear search: best-case Ω(1) if target is first, worst-case O(n) if target absent, average-case Θ(n) under uniform distribution. Quicksort: average-case Θ(n log n) if pivots are random; worst-case O(n^2) if partitioning is always unbalanced (e.g., choosing extreme pivots on sorted input). Hash tables: average lookup Θ(1) with good hashing; worst-case O(n) if collisions concentrate.

When each measure is used
Use worst-case when inputs can be adversarial or when a strict guarantee is needed. Use average-case when inputs are random or typical and the model is justified. Amortised analysis complements these by averaging costs over sequences rather than input distributions; choose the appropriate method depending on the question asked and state assumptions clearly.

Exam advice
When asked for average-case show the distribution assumption and compute the expected value. For worst-case clearly construct or describe the adversarial input that forces maximum cost. For best-case show the input that gives minimal cost but explain why best-case alone is insufficient for performance assurance.

Defining space complexity
Space complexity measures additional memory used by an algorithm as a function of input size n. Distinguish between total space (including input) and auxiliary space (extra memory the algorithm needs). For many problems auxiliary space is what matters when comparing in-place algorithms to those needing extra buffers.

Counting space usage
Count variables, arrays, recursion stack frames and auxiliary data structures. For recursion, maximum depth times space per call gives stack space. For dynamic allocations count total allocated entries. Express the result in O-notation: O(1) for constant extra space, O(n) for linear extra space, O(n^2) for quadratic space in matrices, and so on.

Common examples
Mergesort typically needs O(n) auxiliary space for merging, while heapsort is in-place with O(1) auxiliary memory. Recursive algorithms may use O(log n) or O(n) stack depending on depth. Adjacency matrix for a graph uses O(n^2) space, whereas adjacency lists use O(n + m) for m edges.

Time-space trade-offs
Some algorithms trade more memory to reduce time, such as memoization in dynamic programming which stores intermediate results to avoid recomputation. Other times low-memory environments require in-place algorithms even if slightly slower. Choose based on resource constraints of the target system.

Practical advice
When asked, clearly state whether you measure auxiliary space or total space. Give counts for arrays and recursion and simplify to asymptotic form. Consider memory locality and cache effects in practical implementations, though these are beyond asymptotic notation but important for performance engineering.

Lower bounds explained
A lower bound shows that no algorithm in a given model can solve a problem faster than a certain asymptotic limit. Lower bounds are important: they tell us when further improvements are impossible under the model's assumptions and guide search for algorithms that meet the bound.

Decision-tree model for comparisons
For comparison-based sorting, model the algorithm as a decision tree where each internal node compares two elements and branches depending on the result. Each leaf represents a possible sorted order. To handle all n! input permutations, the tree must have at least n! leaves, so its height (worst-case number of comparisons) is at least log_2(n!). Using Stirling's approximation log_2(n!) = Θ(n log n), giving a lower bound Ω(n log n) for comparison sorts.

Implications and exceptions
This lower bound applies to any algorithm that only compares elements to determine order. Algorithms that use assumptions about keys, such as integer ranges, can beat this bound: counting sort or radix sort run in O(n + k) or O(n log k) under suitable conditions. Therefore lower bounds depend on the computational model and assumptions allowed.

Other lower bound techniques
Reduction is a technique: show that solving problem B fast would solve problem A which has a known lower bound; hence B also has the lower bound. Adversary arguments, information-theoretic arguments and communication complexity methods are other tools used in proving lower bounds.

Exam style and clarity
When asked for a lower bound, state the model (e.g., comparison-based), give the core argument (decision-tree size or reduction), and derive the asymptotic bound. For sorting, show why at least log_2(n!) comparisons are necessary and then apply Stirling to reach Θ(n log n). Be explicit about assumptions to avoid losing marks.