Question

Solve the following recurrence relation using Recurrence Tree Method.

𝑇(𝑛) = ∫ 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)$