Programming
October 18, 2024Functions
October 18, 2024Functions
| Question 17 |
The time complexity of the following C function is (assume n>0)
int recursive (int n)
{
if (n==1) return(1);
else return(recursive (n-1) + recursive(n-1));
} | O(n) | |
| O(n log n) | |
| O(n2) | |
| O(2n) |
Note ‘a’ is a constant O(1) cost that the non-recursive part of the function takes.
Solving the recurrence by Back Substitution:
T(n) = 2T(n-1)+a
T(n-1) = 2T(n-2)+a
T(n-2) = 2T(n-3)+a
:
:
Thus we can write the equation as follows
T(n) = 2(2T(n-2)+a)+a = 4T(n-2) + 2a + a
T(n) = 4(2T(n-3)+a) + 2a + a = 8T(n-3) + 4a + 2a + a
:
:
:
T(n) = 2k T(n-k) + (2k – 1)a
On substituting limiting condition,
T(1) = 1
=> n – k = 1
=> k = n-1
Therefore, our solution becomes
2n-1 + (2n-1 – 1)a
= O(2n)
Note ‘a’ is a constant O(1) cost that the non-recursive part of the function takes.
Solving the recurrence by Back Substitution:
T(n) = 2T(n-1)+a
T(n-1) = 2T(n-2)+a
T(n-2) = 2T(n-3)+a
:
:
Thus we can write the equation as follows
T(n) = 2(2T(n-2)+a)+a = 4T(n-2) + 2a + a
T(n) = 4(2T(n-3)+a) + 2a + a = 8T(n-3) + 4a + 2a + a
:
:
:
T(n) = 2k T(n-k) + (2k – 1)a
On substituting limiting condition,
T(1) = 1
=> n – k = 1
=> k = n-1
Therefore, our solution becomes
2n-1 + (2n-1 – 1)a
= O(2n)