NIELIT Scientist B 2020 November: 100

Question

Consider the algorithm that solves problems of size $n$ by recursively solving two sub problems of size $n-1$ and then combining the solutions in constant time. Then the running time of the algorithm would be:

• A. $O(n)$
• B. $O(\log n)$
• C. $O(n\log n)$
• D. $O(n^2)$

Answer 1

recurrence relation :

T(n)=2.T(n-1)+c , n>0

T(n)=1, n=0.

as per back substitution method,

T(n) = 2$^k$.T(n-k)+ 2$^{k-1}$c+....+2$^0$c

T(n) = 2$^n$.T(0)+ 2$^{k-1}$c+....+2$^0$c

T(n) =  2$^{n+1}$-1

T(n) =  O(2$^n$)