...
Question 9848 – Time-Complexity
February 13, 2024
Question 9517 – Time-Complexity
February 13, 2024
Question 9848 – Time-Complexity
February 13, 2024
Question 9517 – Time-Complexity
February 13, 2024

Question 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)
A
O(n)
B
O(log n)
C
O(log log n)
D
O(1)
0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x
error: Alert: Content selection is disabled!!