DAA Answers 4 - Recurrences

DAA-Q27 T(n)=T(n-1)+1, T(1)=1 (back-substitution)

=T(n-2)+2=...=T(1)+(n-1)=n -> Theta(n).

DAA-Q28 T(n)=2T(n-1), T(1)=1 (iteration)

=2^(n-1) -> Theta(2^n).

DAA-Q29 T(n)=2T(n/2)+n (recursion tree)

Each of log2 n levels contributes n -> Theta(n log n).

DAA-Q30 Master method: T(n)=8T(n/2)+1000n^3

a=8,b=2,n^(log_b a)=n^3, f=O(n^(3-e)) -> Case 1: Theta(n^3).

DAA-Q31 Master method: T(n)=2T(n/2)+10n

n^(log_b a)=n, f=Theta(n) -> Case 2: Theta(n log n).

DAA-Q32 Master method: T(n)=2T(n/2)+n^2

n^(log_b a)=n, f=Omega(n^(1+e)), a.f(n/b)=n^2/2<=c.n^2 (c=1/2) -> Case 3: Theta(n^2).

DAA-Q33 T(n)=4T(n/2)+n (recursion tree)

Dominated by leaves n^(log_2 4)=n^2 -> Theta(n^2).

Master method: T(n)=aT(n/b)+f(n). Compare f(n) with n^(log_b a): Case 1 smaller -> Theta(n^(log_b a)); Case 2 equal -> Theta(n^(log_b a) log n); Case 3 larger (regularity) -> Theta(f(n)).