Question

(ii) Solve the following recurrence relation using Recurrence Tree Method.

T(n) ={1 if n = 1

T(n/2 ) + n if n > 1}

Show all the steps.

Answer 1

The recursion tree for the given recurrence relation is-

$T(n)- d\\ \downarrow \\ T(\dfrac{n}{2})-d \\\downarrow\\ T(\dfrac{n}{4})-d \\\downarrow\\ T(1)-d \downarrow$

we go like $n,\dfrac{n}{2},\dfrac{n}{4},\dfrac{n}{8}...1$

or $2^k=n, k=log_2n$

So we sum d+d+d.. for $log_2n$ terms complexity $=0 (log_2n)=0(log_2n)$