Question

Q) prove correctness the recurrence relation for case n = 2^x using a proof bt induction.

T(n) if n <= 1 then ....... 0

if n > . 1 . then ............1+4T(n/2)

hint : when n = 2^x each of recursive calls in a given instnace of repetitiveRecursion in on the subproblem of the smae size

the equation n = j-i +1 may be helpful in expressiong the problem size in terms of parameters i and j

the closed-form expression is t(n) = n^2+logn

Answer 1

The problem is not stated properly.

Here's what I understand:

Given:

We need to find the closed form of the recursion when

We can write the recursion as

Now,

Putting

The closed form given in question is wrong.