Solve the following recurrences 1 Tn 4Tn16n 2 Tn Tn11 3 Tn

Solve the following recurrences:

1) T(n) = 4T(n/16)+n

2) T(n) = T(n-1)+1

3) T(n) = T(2n/5)+1

Answer:

1) T(n) = 4T(n/16) + n

Using Masters theorm

Here a = 4 , b = 16 , c = 1 , f(n) = n

log a base b = log 4 base 16 = 1/2

Now c > log a base b , therefore T(n) = theta(f(n) = theta(n)

2) T(n) =T(n -1) + 1

Using Substitution method

T(n -1) = T(n-2) + 1 + 1

T(n) = T(n-2) + 2

T(n -2) = T(n - 3) + 2 + 1

=> T(n) = T(n - 3) + 3

T(n) = T(n - k) + k

Let k = n

T(n) = T(0) + n

=> T(n) = O(n).

3) T(n) = 2T(n/5) + 1

Cannot use Masters theorm , as there is no f(n) , no c