"Asymptotic Complexity & Recurrences" — Practice

Question 1

Which function grows fastest?

Accepted Answer

B

Question 2

Solve T(n) = 4T(n/2) + n.

Accepted Answer

C

Question 3

Which statement is FALSE?

Accepted Answer

D

Question 4

Determine the time complexity of a nested loop where the outer counter i runs from 1 to n doubling each time, and the inner counter j runs from 1 to i doubling each time.

Accepted Answer

Handle the outer loop first. Starting at 1 and doubling until exceeding n gives values 1, 2, 4, 8 and so on, so the outer loop executes log base 2 of n times.

Now the inner loop. For a given outer value i, the inner counter also doubles from 1 up to i, so it executes log base 2 of i times.

Since i takes the values 2 to the 0, 2 to the 1, up to 2 to the k where k is about log n, the inner loop count for the j-th outer iteration is exactly j.

The total is therefore the sum of 1 plus 2 plus 3 up to log n, which is the standard arithmetic series.

That sum is (log n)(log n plus 1) over 2, which is Theta of (log n) squared.

The total complexity is Theta((log n) squared).

The trap is to reason that the outer loop runs log n times and the inner runs up to log n times, giving log n squared — which happens to be right here, but only because the inner count grows linearly in the outer index. Had the inner loop run to i additively rather than by doubling, the total would have been Theta(n) instead, dominated by the final iteration.

Question 5

Solve T(n) = 2T(n/4) + n to the power 0.51 using the master theorem, showing the case and any condition checked.

Accepted Answer

Identify a = 2, b = 4, and f(n) = n to the power 0.51.

Compute the critical exponent: log base 4 of 2 = 0.5, so the critical function is n to the power 0.5, that is the square root of n.

Compare f(n) = n to the 0.51 against n to the 0.5. The first is larger, and the excess is polynomial: n to the 0.51 equals n to the power (0.5 plus 0.01), so epsilon = 0.01 works.

That places us in case 3, which additionally requires the regularity condition.

Check it: a times f(n/b) equals 2 times (n/4) to the 0.51, which is 2 times n to the 0.51 divided by 4 to the 0.51. Since 4 to the 0.51 is slightly more than 2, the coefficient 2 divided by 4 to the 0.51 is slightly less than 1.

A value of c around 0.99 therefore satisfies the condition, and regularity holds.

So T(n) = Theta(n to the power 0.51).

Note how narrow the margin is. Had f(n) been exactly the square root of n, we would be in case 2 with k = 0, giving Theta of root n times log n instead. The 0.01 in the exponent is what moves the answer from a balanced tree to a root-dominated one, which is exactly why the comparison must be polynomial rather than approximate.

Question 6

A stack supports push, pop, and multipop(k) which pops the top k elements or empties the stack if fewer remain. Show that any sequence of n operations costs O(n) in total.

Accepted Answer

A single multipop can cost up to n operations, so the worst-case cost per operation is linear and a naive bound would give O(n squared) for n operations. That bound is not tight.

Use the aggregate method. Observe that every element popped, whether by a pop or by a multipop, must first have been pushed. No element can be popped twice.

Over a sequence of n operations, at most n pushes occur, since each operation performs at most one push. Therefore at most n elements ever enter the stack, and therefore at most n pops occur in total across all pop and multipop calls.

The total work is bounded by the n operations themselves plus the at most n pops they collectively perform, giving at most 2n elementary steps.

So n operations cost O(n) in total, and the amortised cost per operation is O(1).

The accounting method gives the same result with different bookkeeping. Charge 2 units for each push: 1 to perform it and 1 deposited with the element to pay for its eventual pop. Pops and multipops then cost nothing extra, since each popped element carries its own prepaid unit. The balance never goes negative because an element cannot be popped before being pushed, which is exactly the invariant the aggregate argument used.

Question 7

Solve T(n) = T(n/3) + T(2n/3) + n using a recursion tree, and explain why the master theorem cannot be used.

Accepted Answer

The master theorem requires all subproblems to have the same size n over b. Here one subproblem has size n/3 and the other 2n/3, so the recurrence is not of the form a T(n/b) plus f(n) and the theorem simply does not apply.

Build the recursion tree instead. The root does n work. Its two children have sizes n/3 and 2n/3, and their work sums to n/3 plus 2n/3, which is exactly n.

The same holds at every level: the subproblem sizes at any level always sum to n, because each node splits its size into two parts that add back to it. So every full level contributes exactly n.

The number of levels is not uniform, which is the interesting part. Following the shortest path, dividing by 3 each time, the recursion bottoms out after log base 3 of n levels. Following the longest path, multiplying by 2/3 each time, it bottoms out after log base 3/2 of n levels.

So the tree has between log base 3 of n and log base 3/2 of n levels, and both are Theta(log n).

The total is therefore between n times log base 3 of n and n times log base 3/2 of n, both of which are Theta(n log n).

T(n) = Theta(n log n).

The instructive point is that an uneven split does not change the asymptotic result as long as both parts are a constant fraction of the whole. Only a split into a constant-sized piece and the rest, as in worst-case quicksort, degrades to quadratic.

Question 8

Explain why the master theorem fails for T(n) = 2T(n/2) + n/log n, and solve it.

Accepted Answer

Identify a = 2, b = 2, so the critical exponent is log base 2 of 2 = 1 and the critical function is n.

Compare f(n) = n over log n against n. The function f is smaller, which suggests case 1. But case 1 requires f to be polynomially smaller, that is f = O(n to the power 1 minus epsilon) for some positive epsilon.

The ratio of the critical function to f is n divided by (n over log n), which is log n. For case 1 to apply, that ratio would have to grow at least as fast as n to some positive power. It does not: log n grows more slowly than n to the epsilon for every positive epsilon.

Case 2 also fails, since f is not Theta of n times a power of log n — it is n divided by log n, which is n times log to the power minus 1, and case 2 requires k at least 0.

So the recurrence falls in the gap between cases 1 and 2, and the theorem gives no answer.

Solve by recursion tree. At level i there are 2 to the i nodes, each of size n over 2 to the i. The work at that node is (n over 2 to the i) divided by log(n over 2 to the i), which is (n over 2 to the i) divided by (log n minus i).

Multiplying by the 2 to the i nodes gives level work of n divided by (log n minus i).

Summing over i from 0 to log n minus 1 gives n times the sum of 1 over (log n minus i), which reindexes to n times the harmonic series up to log n.

The harmonic series up to m is Theta(log m), so the total is n times Theta(log log n).

T(n) = Theta(n log log n).

Question 9

Prove by substitution that T(n) = T(n/2) + T(n/4) + n is O(n), showing why the naive hypothesis fails and how to strengthen it.

Accepted Answer

Guess T(n) at most c n and attempt the induction.

Assume the bound for smaller arguments: T(n/2) at most c n over 2, and T(n/4) at most c n over 4.

Substitute: T(n) at most c n over 2 plus c n over 4 plus n, which is (3c over 4) n plus n.

For the bound to close we need (3c over 4) n plus n at most c n, that is 3c over 4 plus 1 at most c, giving 1 at most c over 4, so c at least 4.

The induction does close here with c = 4, so the naive hypothesis actually succeeds for this recurrence — the slack of c over 4 was enough to absorb the additive n.

Contrast with a recurrence where it fails, such as T(n) = 2T(n/2) plus n, whose true bound is n log n rather than n. Guessing c n gives 2 times c n over 2 plus n, which is c n plus n, exceeding c n for every c. The induction cannot close, correctly signalling that the guess is wrong.

Where strengthening genuinely helps is a case like T(n) = 2T(n/2) plus 1, whose answer is Theta(n). Guessing T(n) at most c n gives c n plus 1, which exceeds c n. Strengthening the hypothesis to T(n) at most c n minus d gives 2(c n over 2 minus d) plus 1, which is c n minus 2d plus 1, and that is at most c n minus d provided d at least 1.

The pattern is that subtracting a lower-order term creates extra slack that the additive work can consume, which is why a correct guess sometimes needs a stronger hypothesis rather than a different bound.

Practice — "Asymptotic Complexity & Recurrences"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities