2 Consider the following recurrence Tn 2 for n2 2Tn2n for n

2. Consider the following recurrence: T(n) = {2 for n=2 2T(n/2)+n for n=2^k, k>1 Prove using mathematical induction that the solution to the recurrence is T(n) = n log2 n. 3. Use the master theorem to calculate the solution to the recurrence in the previous exercise.

Solution

(2)

T(2)=2

T(n)=2T(n/2)+2

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

T(n)=2{2T(n/4)+2)+2

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

T(n)=4T(n/4)+6

simillarly on moving ahead

we will find general form as

T(n)=T(n/2^k)+nk+n where n=2^k

so reccurence is

T(n)=nlog₂n

(3)

using master theorem,

given

T(n)=2T(n/2)+n,

according to master theorem

T(N) = aT(n/b) + f(n) where a ?1, b >1, f(N) ? 0, then

1. If f(N) = O(N^log_ba - ?) for ? > 0, then T(N) = ?(N^log_ba)

2. If f(N) = ?(N^log_ba), then T(N) = ?(N^log_ba log N)

3. If f(N) = ?(N^log_ba + ?) for ? > 0, and

if a