Hi,
I need help with the following:
Solve the following recurrences, the answers should be in theta notation. For each of them, assume the base case T(x) = 1 for x <= 5.
(a) T(n) = 2T(n − 3) + 1/n
(b) T(n) = n^(1/2) T(n^(1/4)) + n
The following is what i tried:
a) =2T(n-3)+n^(-1) by unrolling i'll get: T(n)=n^(-1)+2(n-3)^(-1)+2(n-6)^-1 +...........+1, which are n/3 terms Then i have to show that T(n)<... and T(n)>...... to conclude that T(n) is theta ...
b) i have no clue how to even start doing it