xyz Interview Question
xyzsCountry: United States
Well, one way to analyze it would be to set up the recurrence equation that reflects the number of recursive calls the algorithm makes: T(1) = O(1) and T(n) = 2*T(n-1) for n>1.
An easy induction shows T(n) = 2^{n-1}, so the algorithm makes O(2^n) recursive calls, which is also its running time as it takes O(1) time within each call.
You can find out the time complexity of above algorithm by solving following equation :
- Rajeev Jayaswal February 24, 2015T(n) = T(n-1) + T(n-1) + const.
You are likely to get T(n) = O(2^n).