Handbooks / Data Structures & Algorithms / Chapter 1

Big-O and Recursion

7 pages · ~5 min✓ Reviewed

Start here. Next up: Arrays and Hashing.

Data Structures & AlgorithmsPage 1

Asymptotic Notation and Growth Rates

1. The Three Bounds

Big-O: f(n)=O(g(n)) if f ≤ c·g(n) for all n ≥ n0
An upper bound, usually quoted for the worst case
Omega is the lower bound: f ≥ c·g(n)
Theta is the tight bound: true only when O and Omega both hold

Symbol	Bound	Means
O	upper	at most g
Omega	lower	at least g
Theta	tight	O and Omega

2. Simplify and Order

Drop constants and lower-order terms: 3n²+5n+9 is Theta(n²)
Different input variables stay separate: O(a+b), not O(n)

Growth order, slowest to fastest

11
2log n
3n
4n log n
5n²
6n³
72ⁿ
8n!

Data Structures & AlgorithmsPage 2

Analysing Loops and Amortised Cost

1. Counting Loops

Data Structures & AlgorithmsPage 3

The Call Stack and Recursion Anatomy

1. Stack Frames

Data Structures & AlgorithmsPage 4

Recursion Trees and Recurrences

1. Recurrence Shape

Data Structures & AlgorithmsPage 5

Master Theorem

1. The Setup

Data Structures & AlgorithmsPage 6

Tail Recursion, Stack Overflow and Cheat Sheet

1. Tail Calls and TCO

Data Structures & AlgorithmsPage 7

Shape	Cost
Loop to n	O(n)
Nested, both to n	multiply: O(n²)
Sequential loops	add, larger wins
i doubles or halves	O(log n)

	Amortised	Average case
Holds for	every sequence	assumed input distribution
Randomness	none	yes

Recurrence	Work per level	Result
`T(n)=2T(n/2)+n` (merge sort)	n on each of log n levels	Theta(n log n)
`T(n)=T(n-1)+1`	1 per level, n levels	O(n)
`T(n)=T(n-1)+n`	n, n-1, ... 1	O(n²)
`T(n)=T(n-1)+T(n-2)+1`	subproblems repeat	about O(2ⁿ)

Case	f(n)	Result	Example
1	polynomially smaller	Θ(n^(log_b a))	leaves dominate
2	= Θ(n^(log_b a))	Θ(n^(log_b a) · log n)	merge sort: Θ(n log n)
3	polynomially larger + regularity	Θ(f(n))	T=2T(n/2)+n²: Θ(n²)

Language	TCO?
Scheme	guaranteed
Some C compilers	sometimes
Python, Java	never

Big-O and Recursion

Asymptotic Notation and Growth Rates

1. The Three Bounds

2. Simplify and Order

Analysing Loops and Amortised Cost

1. Counting Loops

The Call Stack and Recursion Anatomy

1. Stack Frames

Recursion Trees and Recurrences

1. Recurrence Shape

Master Theorem

1. The Setup

Tail Recursion, Stack Overflow and Cheat Sheet

1. Tail Calls and TCO

Check yourself

3. Big-O Is Not Worst Case

2. Amortised Cost

3. Interview Point

2. Anatomy

3. Mistakes

2. Recursion Tree Method

3. Naive Fibonacci

2. The Three Cases

3. When It Fails

2. Stack Overflow

3. Cheat Sheet

Topic	Remember
O / Omega / Theta	upper / lower / tight
Binary search	O(log n)
Good sorts	O(n log n)
Dynamic array append	O(1) amortised
Master theorem	compare f(n) with n^(log_b a)
Recursion space	= depth