The time complexity of the following C function is (assume n > 0 (GATE CS 2004)
int recursive (mt n) { if (n == 1) return (1); else return (recursive (n-1) + recursive (n-1)); } |
(A) 0(n)
(B) 0(nlogn)
(C) 0(n^2)
(D) 0(2^n)
Answer: (D)
Explanation: Recursive expression for the above program will be.
T(n) = 2T(n-1) + c T(1) = c1.
Let us solve it.
T(n) = 2(2T(n-2) + c) + c = 4T(n-2) + 3c T(n) = 8T(n-3) + 6c + c = 8T(n-3) + 7c T(n) = 16T(n-4) + 14c + c = 16T(n-4) + 15c ............................................................ ............................................................. T(n) = (2^(n-1))T(1) + (2^(n-1) - 1)c T(n) = O(2^n)
Whether you’re preparing for your first job interview or aiming to upskill in this ever-evolving tech landscape, neveropen Courses are your key to success. We provide top-quality content at affordable prices, all geared towards accelerating your growth in a time-bound manner. Join the millions we’ve already empowered, and we’re here to do the same for you. Don’t miss out – check it out now!
