Problem Set 6

Recurrences 2

1 Master Method Recurrences

For each of the recurrences Ti below, find fi such that Ti=Θ(fi). Prove your work. Use the master method.

1.1

T1(n)=2T1(n/2)+n4

Solution

Apply the master theorem with a=2,b=2,f(n)=n4. Note that nlog2(2)=n We have n4=Ω(n1+ϵ), so we are in the root heavy case.

To check that the regularity condition holds, we need to check that af(n/b)cf(n) for some c<1 and all sufficiently large n. We have 2(n/2)4=n4/8, so we can take c=1/8.

Thus, the master theory applies and we have T1(n)=Θ(n4).

1.2

T2(n)=7T2(n/2)+n2

Solution Apply the master theorem with a=7,b=2,f(n)=n2. Note that nlog2(7)=n2.81 We have n2=O(nlog2(7)ϵ), so we are in the leaf heavy case. Thus T2(n)=Θ(nlog2(7)).

1.3

T3(n)=2T3(n/4)+n

Solution

Apply the master theorem with a=2,b=4,f(n)=n. Note that nlog4(2)=n. We have f(n)=Θ(nlog4(2)) so we are in the balanced case of the master theorem. Thus, T3(n)=Θ(nlog(n)).

2 Unbalanced Recurrences

2.1

Use any method you want to solve the following recurrence. T(n)=n+T(n/5)+T(7n/10)

By ‘solve the recurrence’, I mean find f such that T(n)=Θ(f).

Solution

Claim. T(n)=Θ(n).

Note that T(n)=Ω(n) since T(n)=n+T(n/5)+T(7n/10)n, since T is positive.

Thus, to show that T(n)=Θ(n) it suffices to show that T(n)=O(n). Use the substitution method. T(n)=n+T(n/5)+T(7n/10)n+cn/5+7cn/10=(1+9c/10)n

We need this expression to be at most cn. Solving for c we need c10.