Question 9848 – Time-Complexity
February 13, 2024Question 9517 – Time-Complexity
February 13, 2024Question 9704 – Time-Complexity
The running time of the following algorithm
Procedure A(n) If n <= 2 return(1) else return (A(⌈√n⌉));
is best described by:
Correct Answer: C
Question 15 Explanation:
T(n) = T(√n)+1
Let n=2m
So, T(2m) = T(2m/2)+1
We substitute T(2m) = S(m),
So now the equation becomes,
S(m) = S(m/2)+1
Now after applying master’s theorem,
S(m) = O(log m)
T(n) = O(log log n)
Let n=2m
So, T(2m) = T(2m/2)+1
We substitute T(2m) = S(m),
So now the equation becomes,
S(m) = S(m/2)+1
Now after applying master’s theorem,
S(m) = O(log m)
T(n) = O(log log n)
O(n)
O(log n)
O(log log n)
O(1)
Subscribe
Login
0 Comments