Complexity Analysis Workshop

Retrieval Prompts

1. State from memory the formal definition of f(n) = O(g(n)).
2. State the Master Theorem's three cases and the regularity condition for case 3.
3. Write the summation sum_{i=1}^{n} i in closed form and its Theta class.
4. State the difference between amortized cost and average-case cost.
5. Explain why a while i < n: i *= 2 loop is Theta(log n).

Compare and Distinguish

Separate these pairs clearly:

• O(g(n)) versus Theta(g(n)) versus "runs in g(n) time"
• amortized cost versus average-case cost versus worst-case-per-operation cost
• recursion tree method versus Master Theorem (when does each apply?)
• T(n) = T(n-1) + n versus T(n) = 2 T(n/2) + n

Common Mistake Check

Identify the error in each statement:

1. "Because the algorithm is O(n^2), on n = 10 it runs in roughly 100 operations."
2. "T(n) = 2 T(n/2) + n^2 solves to Theta(n^2 log n) by the Master Theorem."
3. "Merging two linked lists of length n is Theta(log n) because we halve the work."
4. "A binary counter's n increments cost Theta(n log n) because each increment flips up to log n bits."
5. "Because my algorithm has the same big-O as quicksort, it will run equally fast in practice."

Mini Application

For each snippet, derive the tightest Theta bound with a written summation:

1. for i in range(n): for j in range(i): for k in range(j): work()
2. for i in range(n): for j in range(n): if j > i: break
3. A recursive function T(n) = T(n/2) + T(n/4) + n
4. A recursive function T(n) = 3 T(n/2) + n
5. A binary-counter increment operation, analyzed amortized over n calls

For each recurrence, choose the best solution method (substitution, recursion tree, or Master Theorem) and justify why.

Evidence Check

This page is complete only if, given any of the snippets above, you can:

• translate to a summation or recurrence without looking up the pattern
• solve that summation or recurrence to Theta class
• defend the bound with a one-paragraph written argument

Integrated Loop-Counting Drill

For each snippet, give the tightest bound and one correctness or cost sentence:

1. Single loop: scan an array once and update a maximum.
2. Nested fixed loop: compare every pair i, j.
3. Additive loops: one loop over n, followed by one loop over m.
4. Triangular loop: for i in range(n): for j in range(i): work().
5. Multiplicative nested loop: for every user, scan every permission.
6. Halving loop: repeatedly divide n by 2 until it reaches 1.
7. Nested halving loop: for each i, run a halving loop over n.

Evidence check: include one small input trace for at least three snippets and explain why constants and lower-order terms disappear only after the exact count is understood.