Programming, Data Structures and Algorithms

Sheet 1

Complexity, Recurrences & Hashing

5 formulas

Key formulas

Master Theorem ☆

\[ T(n) = a\,T(n/b) + f(n) \]

compare f(n) to n^(log_b a) to classify

Binary Search Recurrence ☆

\[ T(n) = T(n/2) + O(1) \;\Rightarrow\; O(\log n) \]

Merge Sort Recurrence ☆

\[ T(n) = 2T(n/2) + O(n) \;\Rightarrow\; O(n \log n) \]

Quicksort Complexity ☆

\[ O(n \log n) \text{ average} \qquad O(n^2) \text{ worst case} \]

Hash Table Load Factor ☆

\[ \alpha = \frac{n}{m} \]

n = entries stored, m = number of buckets

Test your recall

Can you recall the master theorem formula?

Reveal formula

\[ T(n) = a\,T(n/b) + f(n) \]

GATE traps 3 traps

Quicksort's worst case is O(n²)

A naive pivot choice (e.g. always the first element) on already-sorted input drives quicksort to O(n²) -- 'quicksort is O(n log n)' is only the average case.

Hash table O(1) lookup is an average, not a guarantee

Average-case O(1) lookup assumes a good hash function and a low load factor -- worst case (many collisions) degrades to O(n).

Master theorem needs the right case match

f(n) must be compared to n^(log_b a): smaller gives Θ(n^(log_b a)), equal (up to log factors) adds a log n factor, and larger needs the extra regularity condition checked before concluding Θ(f(n)).