Asymptotic-Complexity
October 26, 2023Operating-Systems
October 26, 2023UGC NET CS 2018 JUNE Paper-2
| Question 21 |
The solution of the recurrence relation T(m)=T(3m/4)+1 is :
| θ(lg m) | |
| θ(m) | |
| θ(mlg m) | |
| θ(lglg m) |
Question 21 Explanation:
Using Masters Method:
a=1, b=4/3, k=0, p=0
Here, a = b k
So, T(m) = n log a/ log b log p+1 n
T(m) = θ(log m)
a=1, b=4/3, k=0, p=0
Here, a = b k
So, T(m) = n log a/ log b log p+1 n
T(m) = θ(log m)
Correct Answer: A
Question 21 Explanation:
Using Masters Method:
a=1, b=4/3, k=0, p=0
Here, a = b k
So, T(m) = n log a/ log b log p+1 n
T(m) = θ(log m)
a=1, b=4/3, k=0, p=0
Here, a = b k
So, T(m) = n log a/ log b log p+1 n
T(m) = θ(log m)
Subscribe
Login
0 Comments