asymptotic analysis and recurrence relations short notes

Summary: Solving Recurrence Relations

Summary: Solving Recurrences Substitution Best for rigorous proofs when the bound is easily guessable. Recursion Tree Best for intuitive guesses, especially with unequal subproblems. Master Theorem Fastest for standard divide-and-conquer with clear polynomial gaps. Change of Variables Fallback for Master Theorem failures (e.g., logarithmic gaps). Master Theorem Quick Check: 1. Critical function: n^{l o g_{b} a} 2. f (n) smaller by polynomial \to Case 1 3. f (n) matches exactly \to Case 2 4. f (n) larger by polynomial \to Case 3

Asymptotic Notation Cheat Sheet

Cheat Sheet O Upper (\leq) Ω Lower (\geq) Θ Tight (=) o Strict Upper (<) ω Strict Lower (>) Limit Tool: L = 0 ⟹ o, 0 < L < \infty ⟹ Θ, L = \infty ⟹ ω Critical Simplifications: 2^{l o g_{2} n} = n lo g (n!) = Θ (n lo g n) f + g = Θ (max (f, g))

Loop Analysis Quick Reference

Quick Reference: Loop Complexity Loop Pattern Complexity for i = 1 to n Θ (n) while n > 1: n = n/2 Θ (lo g n) for i = 1; i < n; i = i*2 Θ (lo g n) while n > 1: n = sqrt(n) Θ (lo g lo g n) Nested: n \times n Θ (n^{2}) Nested: n \times lo g n Θ (n lo g n) Dependent: \sum_{i = 1}^{n} i Θ (n^{2}) Geometric: n + n /2 + n /4 + \dots Θ (n) Key principles: Independent nested loops \to multiply iterations Dependent nested loops \to sum iterations Sequential loops \to take maximum complexity Constants do not matter: 100 n = Θ (n) Floors and ceilings do not matter asymptotically Function comparison: f (n) ≪ g (n) ⟺ n \to \infty lim \frac{f ( n )}{g ( n )} = 0

1 more card in this chapter

Asymptotic Analysis and Recurrence Relations Short Notes for GATE CS

Asymptotic Analysis and Recurrence Relations short notes for GATE CS: 4 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Summary: Solving Recurrence Relations

Summary: Solving Recurrences

Substitution

Best for rigorous proofs when the bound is easily guessable.

Recursion Tree

Best for intuitive guesses, especially with unequal subproblems.

Master Theorem

Fastest for standard divide-and-conquer with clear polynomial gaps.

Change of Variables

Fallback for Master Theorem failures (e.g., logarithmic gaps).

Master Theorem Quick Check:

1. Critical function: $n^{l o g_{b} a}$
2. $f (n)$ smaller by polynomial $\to$ Case 1
3. $f (n)$ matches exactly $\to$ Case 2
4. $f (n)$ larger by polynomial $\to$ Case 3

Asymptotic Notation Cheat Sheet

Cheat Sheet

$O$ Upper (

\leq

) $Ω$ Lower (

\geq

) $Θ$ Tight (

=

)

$o$ Strict Upper (

<

) $ω$ Strict Lower (

>

)

Limit Tool:

L = 0 ⟹ o

0 < L < \infty ⟹ Θ

L = \infty ⟹ ω

Critical Simplifications:

2^{l o g_{2} n} = n

lo g (n!) = Θ (n lo g n)

f + g = Θ (max (f, g))

Loop Analysis Quick Reference

Quick Reference: Loop Complexity

Loop Pattern	Complexity
`for i = 1 to n`	$Θ (n)$
`while n > 1: n = n/2`	$Θ (lo g n)$
`for i = 1; i < n; i = i*2`	$Θ (lo g n)$
`while n > 1: n = sqrt(n)`	$Θ (lo g lo g n)$
Nested: $n \times n$	$Θ (n^{2})$
Nested: $n \times lo g n$	$Θ (n lo g n)$
Dependent: $\sum_{i = 1}^{n} i$	$Θ (n^{2})$
Geometric: $n + n /2 + n /4 + \dots$	$Θ (n)$

Key principles:

Independent nested loops $\to$ multiply iterations
Dependent nested loops $\to$ sum iterations
Sequential loops $\to$ take maximum complexity
Constants do not matter: $100 n = Θ (n)$
Floors and ceilings do not matter asymptotically

Function comparison:

f (n) ≪ g (n) ⟺ n \to \infty lim \frac{f ( n )}{g ( n )} = 0

Exam Strategy: If You See X, Do Y

Exam Strategy: Pattern Recognition

for i = 1 to n

\to

Θ (n)

while n > 1: n = n/2

\to

Θ (lo g n)

for i = 1; i < n; i = i*2

\to

Θ (lo g n)

while n > 1: n = sqrt(n)

\to

Θ (lo g lo g n)

Two nested for loops (both to n)

\to

Θ (n^{2})

Nested loop with inner bound = outer

\to

Sum:

Θ (n^{2})

floor(n/2) or ceil(n/2)

\to

Ignore, treat as

n /2

Geometric series: $n + n /2 + \dots$

\to

Converges to

Θ (n)

Multiple loops in sequence

\to

Take

max

of complexities

Comparing $f (n)$ versus $g (n)$

\to

Compute

lim \frac{f ( n )}{g ( n )}

Final checklist:

[ ] Count iterations correctly
[ ] Check if loops are independent or dependent
[ ] Ignore constants and floors/ceilings
[ ] Use limit method for function comparison
[ ] Verify with small examples if unsure