Every sub-question from every problem — answer hidden until you reveal it.
TIME ANALYSIS Three algorithms · Big-Theta · Master Theorem
Time complexity describes how the number of operations an algorithm performs scales with input size n. We use Big-Theta (Θ) to give a tight bound — meaning the runtime grows at exactly that rate, not faster, not slower, up to constant factors.
The key question for any algorithm is: what is the most deeply nested operation, and how many times does it execute? Everything else is secondary — we drop lower-order terms and constants because for large n, they don't matter.
You will analyze multiplying two n × n matrices using three different algorithms. For each, the goal is to count operations precisely, then express it in Big-Theta notation.
To multiply two n×n matrices A and B into result matrix C, each entry C[i][j] is computed as the dot product of row i of A with column j of B. That dot product requires n multiplications (one per element pair). We do this for every (i,j) entry in C, of which there are n×n = n² entries.
The algorithm uses three nested loops: the outer two iterate over every (i,j) position in C, and the inner loop computes the dot product by accumulating n multiply-add operations. The innermost line is what we count.
Time: Θ(n³) — three nested loops of size n give n³ multiply-add operations. Space: Θ(n²) — result matrix C stores n² values; input matrices are read-only.
Work through the loops from outside in. Each loop multiplies the count:
Intuition: there are n² entries in C, each requiring a dot product of length n. That's n² × n = n³.
Each loop iteration performs constant work (one multiply-add). Since the innermost line runs n³ times total, and the initialization C[i][j]=0 adds only n² work (dominated), the running time is T(n) = n³.
Big-O is an upper bound. Big-Theta is a tight bound — it says the runtime is exactly cubic growth. For iterative matrix multiplication, the loops always run to completion, so the best and worst cases are the same. Theta is the right notation.
Instead of computing each entry one-by-one, divide and conquer breaks the n×n matrices into four (n/2 × n/2) blocks. The product can then be expressed in terms of products of these sub-blocks. This recursion bottoms out at 1×1 matrices (a single scalar multiply).
The key insight: to compute the four blocks of the result matrix C using this block formulation, you need 8 recursive multiplications of (n/2 × n/2) matrices, plus matrix addition work to combine results. Addition of two n×n matrices costs Θ(n²) because you touch every entry exactly once.
The question is: does splitting into subproblems actually reduce the total work? The Master Theorem will tell us.
Matrices are split into four (n/2 × n/2) blocks and multiplied recursively. This requires 8 recursive multiplications plus addition work costing Θ(n²).
Each n×n matrix is divided into four (n/2 × n/2) blocks. To compute the product using block multiplication, 8 recursive multiplications are performed — this comes directly from the block matrix multiplication formula (each of the 4 result blocks requires 2 sub-multiplications).
Each recursive call works on matrices of size n/2 × n/2. We halved both dimensions, so the problem size is n/2.
T(n) is the total work for size n. The "8T(n/2)" term accounts for making 8 recursive calls on half-size problems. The "Θ(n²)" term is the work done at this level: adding/subtracting the sub-matrices to combine results. Every recurrence for divide and conquer follows this pattern: subproblem work + combine work.
The Master Theorem solves recurrences of this form by comparing f(n) (the work done outside recursion) against nlog_b(a) (which represents the total work done at the leaves of the recursion tree).
Critical exponent: logb(a) = log2(8) = 3
Compare f(n) = n² with n3: f(n) grows slower than n3 → Case 1 applies
If f(n) = O(nc−ε) for some ε > 0 where c = logb(a), then T(n) = Θ(nc). This case means the recursion tree's leaves dominate — most of the work happens at the bottom of the tree, not at the top.
Exactly the same as the brute-force iterative algorithm. Dividing into subproblems didn't help here because we still spawn 8 subproblems — the recursion tree has the same total leaf work as just doing it iteratively. The overhead of divide and conquer didn't buy us anything when a=8.
Strassen's key insight is that you can compute the 4 block sub-matrices of C using only 7 multiplications instead of 8, by cleverly reusing intermediate products. This requires computing 7 "helper" matrices (M₁–M₇) using sums/differences of blocks first, then combining them. Each of those 7 helper computations is a single (n/2 × n/2) matrix multiply.
The extra additions and subtractions needed to set up M₁–M₇ and combine them still cost Θ(n²). So the recurrence looks almost identical — except a drops from 8 to 7. That one change has a surprisingly large effect on the exponent.
Strassen's algorithm reduces recursive multiplications from 8 to 7 via algebraic manipulation. Matrix additions/subtractions still cost Θ(n²).
a = 7 instead of 8. Everything else is identical. Saving one recursive call changes the leaf-level work count from 8^depth to 7^depth — which drastically reduces the total work for large n.
Critical exponent: log2(7) ≈ 2.807
Compare f(n) = n² with n2.807:
f(n) = n² grows slower than n2.807 → Case 1 applies
Because f(n) is dominated by the leaf work, T(n) = Θ(nlog₂7).
One fewer multiplication changed the exponent from 3.0 to 2.807. This might seem small, but for large n the difference is enormous. For n = 1000, n³ = 10⁹ while n^2.807 ≈ 3.2 × 10⁸ — about 3× faster. Strassen is asymptotically faster than standard matrix multiplication, which is why it matters theoretically even though constants make it impractical for small n.
T(n) = aT(n/b) + f(n), let c = logb(a)
DYNAMIC PROGRAMMING Bottom-up · m and s tables · Parenthesization
Matrix multiplication is associative: (A×B)×C = A×(B×C). But the cost — number of scalar multiplications — depends heavily on the order you parenthesize. Different orderings can differ by orders of magnitude in cost.
This is a dynamic programming problem because: (1) it has optimal substructure — the optimal solution to the full chain includes optimal solutions to sub-chains, and (2) sub-chains overlap — the same sub-chain appears in many different full-chain calculations, so we cache results in the m table rather than recomputing.
We fill the table in order of increasing chain length, so that when we compute m[i][j], all shorter sub-chains are already solved.
Given: A₁(7×2), A₂(2×9), A₃(9×6), A₄(6×5)
Find the minimum scalar multiplications to compute A₁×A₂×A₃×A₄ and the optimal parenthesization.
Fill tables: m[i][j] (min cost) and s[i][j] (split point k).
p[0]=7, p[1]=2 → A₁ is 7×2 | p[1]=2, p[2]=9 → A₂ is 2×9 | p[2]=9, p[3]=6 → A₃ is 9×6 | p[3]=6, p[4]=5 → A₄ is 6×5. Notice how adjacent dimensions share a value — this is what makes the matrices compatible for multiplication.
Set m[i][i] = 0 for all i. A single matrix requires no multiplication — there is nothing to multiply. The cost of "multiplying" a chain of length 1 is zero by definition. All other cells start empty (to be filled).
| m[i][j] | j=1 | j=2 | j=3 | j=4 |
|---|---|---|---|---|
| i=1 | 0 | ? | ? | ? |
| i=2 | — | 0 | ? | ? |
| i=3 | — | — | 0 | ? |
| i=4 | — | — | — | 0 |
m[1][2]: Only split is k=1
= m[1][1] + m[2][2] + p[0]×p[1]×p[2] = 0 + 0 + 7×2×9 = 126 → s[1][2] = 1
m[2][3]: Only split is k=2
= 0 + 0 + p[1]×p[2]×p[3] = 2×9×6 = 108 → s[2][3] = 2
m[3][4]: Only split is k=3
= 0 + 0 + p[2]×p[3]×p[4] = 9×6×5 = 270 → s[3][4] = 3
| m[i][j] | j=1 | j=2 | j=3 | j=4 |
|---|---|---|---|---|
| i=1 | 0 | 126 | ? | ? |
| i=2 | — | 0 | 108 | ? |
| i=3 | — | — | 0 | 270 |
| i=4 | — | — | — | 0 |
m[1][3] — try k=1 and k=2:
Min = 192 at k=1 → m[1][3] = 192, s[1][3] = 1
m[2][4] — try k=2 and k=3:
Min = 168 at k=3 → m[2][4] = 168, s[2][4] = 3
| m[i][j] | j=1 | j=2 | j=3 | j=4 |
|---|---|---|---|---|
| i=1 | 0 | 126 | 192 | ? |
| i=2 | — | 0 | 108 | 168 |
| i=3 | — | — | 0 | 270 |
| i=4 | — | — | — | 0 |
m[1][4] — try k=1, k=2, k=3:
Min = 238 at k=1 → m[1][4] = 238, s[1][4] = 1
m[i][j] — minimum cost:
| m[i][j] | j=1 | j=2 | j=3 | j=4 |
|---|---|---|---|---|
| i=1 | 0 | 126 | 192 | 238 |
| i=2 | — | 0 | 108 | 168 |
| i=3 | — | — | 0 | 270 |
| i=4 | — | — | — | 0 |
s[i][j] — optimal split point:
| s[i][j] | j=1 | j=2 | j=3 | j=4 |
|---|---|---|---|---|
| i=1 | — | 1 | 1 | 1 |
| i=2 | — | — | 2 | 3 |
| i=3 | — | — | — | 3 |
| i=4 | — | — | — | — |
Read the s table recursively: s[i][j] tells you where to split the chain from i to j.
( A₁ × ((A₂ × A₃) × A₄) ) — total cost: 238 scalar multiplications
Time: Θ(n³) — three nested loops (chain length, start index, split point) each up to n → O(n³) total. Space: Θ(n²) — two n×n tables, m[i][j] for costs and s[i][j] for split points.
DYNAMIC PROGRAMMING Include/exclude decision · Build table row by row · Traceback
In 0/1 Knapsack, each item is either taken whole or not at all. A greedy approach (take best ratio first) does not work here — it can get stuck with a suboptimal combination when partial items aren't allowed.
The DP approach builds a table P[i][w] that answers: "what is the maximum profit using only items 1 through i, with capacity exactly w?" By building this up from i=0 and w=0, each cell can be computed using previously solved sub-problems in O(1) time, giving an overall O(nW) algorithm.
At each cell, you make one binary decision: include item i (if it fits) or exclude it. You take the max of the two choices.
Knapsack capacity: W = 8 lbs, n = 4 items. Maximize profit. Each item taken whole or not at all.
| Item | Profit | Weight |
|---|---|---|
| 1 | 1 | 2 |
| 2 | 2 | 3 |
| 3 | 5 | 4 |
| 4 | 6 | 5 |
Profit = [1, 2, 5, 6] Weight = [2, 3, 4, 5]
Table P[i][w]: i = items considered (0 to n=4), w = capacity (0 to W=8)
Dimensions: (n+1) × (W+1) = 5 × 9
Initialize all to 0. Row 0 (no items) is trivially all zeros — with no items available, profit is always 0.
If Weight[i] > w (item too heavy): P[i][w] = P[i−1][w]
Otherwise: P[i][w] = max( P[i−1][w] , Profit[i] + P[i−1][w − Weight[i]] )
Exclude: take best profit from row above (same capacity) = P[i−1][w]. We pretend item i doesn't exist.
Include: take this item's profit, then look up the best profit achievable with the remaining capacity = Profit[i] + P[i−1][w − Weight[i]]. We "use up" Weight[i] capacity and get Profit[i] in return.
Take the max of the two options — DP always records the best achievable.
w=0,1: Weight[1]=2 > w → can't fit → copy 0 from row above
w=2: max(P[0][2], 1 + P[0][0]) = max(0, 1+0) = 1
w=3: max(P[0][3], 1 + P[0][1]) = max(0, 1+0) = 1
w=4–8: same logic, always max(0, 1) = 1
| i\w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
w=0,1,2: Weight[2]=3 > w → copy row above: 0, 0, 1
w=3: max(P[1][3], 2+P[1][0]) = max(1, 2+0) = 2
w=4: max(P[1][4], 2+P[1][1]) = max(1, 2+0) = 2
w=5: max(P[1][5], 2+P[1][2]) = max(1, 2+1) = 3
w=6: max(P[1][6], 2+P[1][3]) = max(1, 2+1) = 3
w=7: max(P[1][7], 2+P[1][4]) = max(1, 2+1) = 3
w=8: max(P[1][8], 2+P[1][5]) = max(1, 2+1) = 3
| i\w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 3 |
w=0–3: Weight[3]=4 > w → copy row above: 0,0,1,2
w=4: max(P[2][4], 5+P[2][0]) = max(2, 5+0) = 5
w=5: max(P[2][5], 5+P[2][1]) = max(3, 5+0) = 5
w=6: max(P[2][6], 5+P[2][2]) = max(3, 5+1) = 6
w=7: max(P[2][7], 5+P[2][3]) = max(3, 5+2) = 7
w=8: max(P[2][8], 5+P[2][4]) = max(3, 5+2) = 7
| i\w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| 2 | 0 | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 3 |
| 3 | 0 | 0 | 1 | 2 | 5 | 5 | 6 | 7 | 7 |
w=0–4: Weight[4]=5 > w → copy row above: 0,0,1,2,5
w=5: max(P[3][5], 6+P[3][0]) = max(5, 6+0) = 6
w=6: max(P[3][6], 6+P[3][1]) = max(6, 6+0) = 6
w=7: max(P[3][7], 6+P[3][2]) = max(7, 6+1) = 7
w=8: max(P[3][8], 6+P[3][3]) = max(7, 6+2) = 8 ← final answer
| i\w | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 3 |
| 3 | 0 | 0 | 1 | 2 | 5 | 5 | 6 | 7 | 7 |
| 4 | 0 | 0 | 1 | 2 | 5 | 6 | 6 | 7 | 8 |
Traceback rule: at P[i][w], if P[i][w] ≠ P[i-1][w], then item i was included. Subtract its weight and move to row i-1. If equal, item i was excluded — move up a row, same column.
Item 2 (Profit=2, Weight=3) + Item 4 (Profit=6, Weight=5)
Total Weight = 8 lbs ✓ Total Profit = 8 ✓
Time: Θ(nW) — two nested loops: n items × W+1 capacities, each cell filled in O(1). Space: Θ(nW) — the full (n+1)×(W+1) table P; reducible to Θ(W) if only the final value is needed (not the traceback).
GREEDY Frequency count · Min-heap tree · Variable-length codes · Compression
In a fixed-length encoding, every character gets the same number of bits (e.g., ASCII uses 8). Huffman encoding assigns shorter codes to more frequent characters and longer codes to rare ones, minimizing the total bits needed to encode a message.
It's greedy: at each step, merge the two lowest-frequency nodes in the priority queue into a new internal node. This builds a binary tree where the path from root to a leaf is the code for that character. The greedy choice (always merge the two smallest) is provably optimal.
The result is a prefix-free code — no code is a prefix of another — which means encoded bitstrings can be decoded unambiguously without delimiters.
Apply Huffman compression to the string "balloon" (case-insensitive).
Steps: (a) count frequencies, (b) build tree, (c) assign codes, (d) encode string, (e) compare with fixed-length encoding.
| Character | Frequency |
|---|---|
| b | 1 |
| a | 1 |
| l | 2 |
| o | 2 |
| n | 1 |
7 total characters, 5 unique characters. b-a-l-l-o-o-n: b=1, a=1, l=2, o=2, n=1.
Queue: b(1), a(1), n(1), l(2), o(2)
Merge 1: Take two smallest → b(1) + n(1) → internal node bn(2)
Queue: a(1), bn(2), l(2), o(2)
Merge 2: Take two smallest → a(1) + bn(2) → internal node abn(3)
Queue: l(2), o(2), abn(3)
Merge 3: Take two smallest → l(2) + o(2) → internal node lo(4)
Queue: abn(3), lo(4)
Merge 4: abn(3) + lo(4) → root(7)
l and o have the highest frequency (2), so they end up closest to the root and get the shortest codes. b and n are deepest, getting the longest codes. This assignment minimizes total bits: frequent chars pay less per occurrence.
Traverse from root: left = 0, right = 1
| Char | Freq | Code | Bits |
|---|---|---|---|
| l | 2 | 00 | 2 |
| o | 2 | 01 | 2 |
| a | 1 | 10 | 2 |
| b | 1 | 110 | 3 |
| n | 1 | 111 | 3 |
b → 110
a → 10
l → 00
l → 00
o → 01
o → 01
n → 111
Fixed-length formula: ⌈log&sub2;(N)⌉ bits per character, where N = number of unique characters
5 unique characters → ⌈log&sub2;(5)⌉ = ⌈2.32⌉ = 3 bits per character
Total: 7 characters × 3 bits = 21 bits
| Method | Total Bits |
|---|---|
| Fixed-length | 21 bits |
| Huffman | 16 bits |
| Savings | 5 bits (≈24% smaller) |
Huffman reduces size from 21 to 16 bits because l and o (frequency 2) get 2-bit codes instead of 3-bit codes — saving 1 bit per occurrence, 4 total. That's exactly the 5-bit improvement (l saves 2×1, o saves 2×1, a also gets a 2-bit code saving 1 bit).
Time: Θ(n log n) — n−1 iterations, each with two Extract-Min and one Insert on a heap of size ≤n → O(log n) each. Space: Θ(n) — the tree has 2n−1 nodes total (n leaves + n−1 internal nodes).
GREEDY Profit/weight ratio · Sort descending · Take fractions when needed
Unlike 0/1 Knapsack, you can take any fraction of an item. This changes everything: it means you never "waste" capacity. Once you fill the knapsack optimally up to the last item, you fill the remainder with a fraction of the next best item.
The greedy strategy — sort by profit/weight ratio and take the best available — is provably optimal. The argument: if you didn't take the item with the best ratio first, you could swap it in for whatever you did take and improve profit. Therefore, always taking the highest-ratio item first can never be wrong.
Time complexity is O(n log n) due to sorting; the greedy selection itself is O(n).
Capacity: 15 lbs, n=7 items. You may take fractions of items. Maximize total profit using a greedy strategy.
| Item | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| Profit | 12 | 8 | 20 | 10 | 7 | 25 | 4 |
| Weight | 3 | 4 | 8 | 7 | 1 | 5 | 2 |
| Item | Profit | Weight | Ratio (P/W) |
|---|---|---|---|
| 1 | 12 | 3 | 4.00 |
| 2 | 8 | 4 | 2.00 |
| 3 | 20 | 8 | 2.50 |
| 4 | 10 | 7 | 1.43 |
| 5 | 7 | 1 | 7.00 |
| 6 | 25 | 5 | 5.00 |
| 7 | 4 | 2 | 2.00 |
| Rank | Item | Profit | Weight | Ratio |
|---|---|---|---|---|
| 1st | 5 | 7 | 1 | 7.00 |
| 2nd | 6 | 25 | 5 | 5.00 |
| 3rd | 1 | 12 | 3 | 4.00 |
| 4th | 3 | 20 | 8 | 2.50 |
| 5th | 2 | 8 | 4 | 2.00 |
| 6th | 7 | 4 | 2 | 2.00 |
| 7th | 4 | 10 | 7 | 1.43 |
Remaining capacity = 15. Item 5 weighs 1 lb. 1 ≤ 15 → fits entirely. Take 100%.
Total Weight = 1 lb Total Profit = 7
Remaining capacity = 14. Item 6 weighs 5 lbs. 5 ≤ 14 → fits entirely. Take 100%.
Total Weight = 6 lbs Total Profit = 7 + 25 = 32
Remaining capacity = 9. Item 1 weighs 3 lbs. 3 ≤ 9 → fits entirely. Take 100%.
Total Weight = 9 lbs Total Profit = 32 + 12 = 44
Remaining capacity = 6 lbs. Item 3 weighs 8 lbs. Does NOT fit entirely.
Fraction = remaining / weight = 6/8 = 0.75
Profit from fraction = 20 × 0.75 = 15
Total Weight = 9 + 6 = 15 lbs (knapsack full)
Total Profit = 44 + 15 = 59
| Item | Fraction Taken | Weight | Profit |
|---|---|---|---|
| 5 | 100% | 1 lb | 7 |
| 6 | 100% | 5 lbs | 25 |
| 1 | 100% | 3 lbs | 12 |
| 3 | 75% | 6 lbs | 15 |
Total Weight = 15 lbs ✓ Total Profit = 59 units
Greedy works here because fractions are allowed — you never waste capacity. In 0/1 Knapsack, greedy fails because taking the best-ratio item whole can leave capacity that no remaining item fits into optimally. Fractional knapsack is O(n log n); 0/1 knapsack requires O(nW) DP.
Time: Θ(n log n) — dominated by the sort; the greedy selection loop is O(n). Space: Θ(n) — stores the ratio and sorted order for all n items.