Week 12: Algorithm Design & Analysis

1. Asymptotic Notation & Complexity Analysis

Big-O (O) describes an upper bound on growth rate (worst case, or a general bound). Big-Omega (Ω) describes a lower bound (best case, or a guarantee that the algorithm takes at least this long). Big-Theta (Θ) describes a tight bound — both upper and lower — meaning the algorithm's growth rate is exactly this, not just bounded above or below by it. A very common trap: saying an algorithm "is O(n log n)" doesn't mean it's exactly n log n — O only claims an upper bound, so technically an O(1) algorithm is also O(n log n); Θ is the notation that pins the growth rate down exactly.

Standard complexity classes in increasing order of growth: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!). Recognising which of your own code falls into which class — usually by counting nested loops (each nested loop over n typically multiplies by another factor of n) — is the practical skill this maps to.

solving a recurrence with the Master Theorem

T(n) = a*T(n/b) + f(n)      (Master Theorem form)

Compare f(n) against n^(log_b a):

Case 1: f(n) = O(n^(log_b a - eps))       ->  T(n) = Theta(n^(log_b a))
Case 2: f(n) = Theta(n^(log_b a))         ->  T(n) = Theta(n^(log_b a) * log n)
Case 3: f(n) = Omega(n^(log_b a + eps))   ->  T(n) = Theta(f(n))

Example -- Merge Sort: T(n) = 2T(n/2) + O(n)
  a=2, b=2  ->  n^(log_2 2) = n^1 = n
  f(n) = O(n) matches Case 2 exactly
  => T(n) = Theta(n log n)

A precise way to say it in an exam answer

"Best case" pairs naturally with Ω, "worst case" pairs naturally with O, and a tight, single-growth-rate claim (as in most textbook algorithm summaries) is technically a Θ statement — even when people casually say "O(n log n)" for it.

2. Divide & Conquer, Greedy & Dynamic Programming

Divide & conquer splits a problem into independent subproblems, solves each recursively, and combines results (merge sort, quick sort, binary search). Greedy algorithms make the locally optimal choice at each step, hoping it leads to a global optimum — this only works when the problem has the greedy-choice property and optimal substructure (Dijkstra's shortest path, Kruskal's/Prim's minimum spanning tree, Huffman coding all qualify; the 0/1 knapsack problem famously does NOT, needing DP instead).

Dynamic programming (DP) solves problems with overlapping subproblems and optimal substructure by solving each distinct subproblem once and storing ("memoizing") the result, avoiding the exponential blow-up of recomputing it repeatedly. The classic diagnostic: if the naive recursive solution recomputes the exact same subproblem many times (e.g. plain recursive Fibonacci recomputes fib(n-2) many times over), that's a strong signal DP applies and will collapse exponential time to polynomial.

3. Graph Algorithms, Backtracking & NP-Completeness

Standard graph algorithms: BFS (level-by-level, uses a queue, finds shortest path in an unweighted graph), DFS (goes deep before wide, uses a stack/recursion, used for cycle detection and topological sort), Dijkstra's algorithm (single-source shortest path with non-negative weights, greedy), and Kruskal's/Prim's algorithms (minimum spanning tree, both greedy but built differently — Kruskal sorts all edges globally and adds if no cycle forms, Prim grows one connected tree outward). Backtracking (N-Queens, Sudoku) systematically builds candidate solutions and abandons ("backtracks" from) a branch the moment it's known to be invalid, pruning the search space compared to brute force.

P is the class of problems solvable in polynomial time. NP is the class of problems whose proposed solution can be verified in polynomial time (whether or not it can be solved that fast). A problem is NP-complete if it's in NP and every other NP problem can be reduced to it in polynomial time — meaning an efficient solution to any one NP-complete problem would give an efficient solution to all of them. Classic NP-complete problems: SAT (Boolean satisfiability, the first proven NP-complete problem via Cook's theorem), the Travelling Salesman Problem (decision version), the 0/1 Knapsack problem (decision version), and the Hamiltonian Cycle problem. Whether P = NP remains one of the most famous open problems in computer science.

NP does not mean "not solvable in polynomial time"

NP means a proposed solution can be VERIFIED quickly — it says nothing by itself about whether a solution can be FOUND quickly. Every problem in P is also in NP (if you can solve it fast, you can trivially verify a solution fast too) — the open question is only whether NP problems can also always be solved, not just verified, in polynomial time.

4. Hands-on Exercise

Hands-on

Classify problems by design technique and trace an NP-completeness argument

This unit is tested mostly through recognition — given a problem, name the right technique and justify it.

Part 1 — Technique classification:

For each of these, name the best-fit design technique and why: (a) finding the kth smallest element in an unsorted array, (b) making change with the fewest coins for a "nice" currency system, (c) finding the longest common subsequence of two strings, (d) solving a maze by trying paths and undoing dead ends.
For the 0/1 knapsack problem specifically, explain in your own words why a greedy "always take the highest value-per-weight item" strategy can fail — construct a small 3-item counterexample.

Part 2 — Complexity growth:

Given T(n) = 4T(n/2) + n, use the Master Theorem to find Θ(T(n)).
Rank these five growth rates from slowest to fastest-growing: O(n log n), O(2ⁿ), O(n²), O(log n), O(n).

5. Exam-Style Practice (UGC NET Pattern)

Five NTA-pattern questions on complexity notation, design techniques and NP-completeness.

Which asymptotic notation specifically represents a tight bound — i.e. both an upper and a lower bound on an algorithm's growth rate?

A) Big-O (O)
B) Big-Omega (Ω)
C) Big-Theta (Θ)
D) Little-o (o)

Correct answer: C) Big-Theta (Θ). Big-Theta (Θ) is the notation for a tight bound, meaning the function is bounded both above and below by the same growth rate — Big-O gives only an upper bound and Big-Omega only a lower bound.

Using the Master Theorem on T(n) = 2T(n/2) + O(n), what is Θ(T(n))?

A) Θ(n)
B) Θ(n log n)
C) Θ(n²)
D) Θ(log n)

Correct answer: B) Θ(n log n). With a=2, b=2, f(n)=O(n): n^(log_2 2) = n, and f(n)=Θ(n) matches this exactly, which is Master Theorem Case 2, giving Θ(n log n) — this is exactly merge sort's complexity.

Which classic optimization problem is famous for NOT being solvable optimally by a simple greedy strategy, requiring dynamic programming instead?

A) Minimum spanning tree (Kruskal's)
B) 0/1 Knapsack problem
C) Single-source shortest path (Dijkstra's)
D) Huffman coding

Correct answer: B) 0/1 Knapsack problem. The 0/1 knapsack problem does not have the greedy-choice property (you can't always safely take the best value-per-weight item, since items can't be split) and requires dynamic programming for a guaranteed optimal solution; the other three are classic greedy-algorithm successes.

A problem is in the complexity class NP if:

A) It cannot be solved by any computer in any amount of time
B) A proposed solution to it can be verified in polynomial time
C) It can only be solved using dynamic programming
D) It has exactly one correct solution

Correct answer: B) A proposed solution to it can be verified in polynomial time. NP is defined by verifiability: a problem is in NP if, given a proposed solution, that solution can be checked for correctness in polynomial time — this says nothing directly about how fast a solution can be found.

Which of the following is considered the first problem proven to be NP-complete (via Cook's theorem)?

A) Travelling Salesman Problem
B) Boolean Satisfiability (SAT)
C) 0/1 Knapsack
D) Hamiltonian Cycle

Correct answer: B) Boolean Satisfiability (SAT). Boolean Satisfiability (SAT) was the first problem proven NP-complete, by Stephen Cook in 1971 — all other NP-completeness proofs (including TSP, Knapsack and Hamiltonian Cycle) proceed by reducing SAT (or another already-proven NP-complete problem) to the new problem.