Question 9570 – Time-Complexity
February 13, 2024Question 9573 – Time-Complexity
February 13, 2024Question 9571 – Time-Complexity
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));
} Correct Answer: D
Question 22 Explanation:
if (n==1)
return(1)
else
return(recursive(n-1) + recursive(n-1))
n>0:
T(2) = T(1) + T(1) = 2T(1)
T(3) = T(2) + T(2) = 2T(2) = 2⋅2T(1) = 22T(1)
T(4) = 23⋅T(1)
⋮
T(n) = 2n⋅T(1) = O(2n)
return(1)
else
return(recursive(n-1) + recursive(n-1))
n>0:
T(2) = T(1) + T(1) = 2T(1)
T(3) = T(2) + T(2) = 2T(2) = 2⋅2T(1) = 22T(1)
T(4) = 23⋅T(1)
⋮
T(n) = 2n⋅T(1) = O(2n)
O(n)
O(n log n)
O(n2)
O(2n)
Subscribe
Login
0 Comments