Introduction
When we design an algorithm, the most important question an exam (and real life) asks is: how does the running time or memory grow as the input gets bigger? We do not care that one machine is faster than another, or that C is faster than Python — those are constant factors. We care about the shape of the growth: does the work double when the input doubles, or does it get four times bigger, or a million times bigger?
Asymptotic analysis is the mathematical language for describing this growth, and recurrences are the tool for finding the growth of recursive algorithms (like Merge Sort or Binary Search). Together they are the single most tested topic in the "Algorithms" section of BCS, Bank IT, and IT-officer written and MCQ exams. Almost every question about "time complexity", "Big-O", "order of growth", or "solve the recurrence" comes straight from here.
Learning Objectives
- Define Big-O (O), Big-Omega (Ω), and Big-Theta (Θ) precisely and explain the intuition behind each.
- Rank the common growth functions from slowest to fastest growing.
- Compute the time complexity of loops, nested loops, and simple code fragments.
- Distinguish best case, worst case, and average case, and relate them to O, Ω, Θ.
- Set up a recurrence relation from a recursive algorithm.
- Solve recurrences by the substitution method, the recursion-tree method, and the Master Theorem.
- Avoid the classic exam traps (e.g. "Big-O means worst case").