Algorithms
October 12, 2023Algorithms
October 12, 2023Algorithms
| Question 6 |
For parameters a and b, both of which are ω(1), T(n) = T(n1/a)+1, and T(b)=1.
Then T(n) is
| θ(loga logb n) | |
| θ(logb loga n)
| |
| θ(log2 log2 n)
| |
| θ(logab n)
|
Question 6 Explanation:
T(n) = T(n1/a+1, T(b) = 1
T(n) = [T(n1/a2)+1] + 1
= [T(n1/a3)+1] + 2
= [T(n1/a3)] + 3
= [T(n1/ak)] + b
= logb n = ak
= log logb n = k log a
= k= loga logb n
T(n)=1+loga logb n
T(n)=O(loga logb n)
T(n) = [T(n1/a2)+1] + 1
= [T(n1/a3)+1] + 2
= [T(n1/a3)] + 3
= [T(n1/ak)] + b
= logb n = ak
= log logb n = k log a
= k= loga logb n
T(n)=1+loga logb n
T(n)=O(loga logb n)
Correct Answer: A
Question 6 Explanation:
T(n) = T(n1/a+1, T(b) = 1
T(n) = [T(n1/a2)+1] + 1
= [T(n1/a3)+1] + 2
= [T(n1/a3)] + 3
= [T(n1/ak)] + b
= logb n = ak
= log logb n = k log a
= k= loga logb n
T(n)=1+loga logb n
T(n)=O(loga logb n)
T(n) = [T(n1/a2)+1] + 1
= [T(n1/a3)+1] + 2
= [T(n1/a3)] + 3
= [T(n1/ak)] + b
= logb n = ak
= log logb n = k log a
= k= loga logb n
T(n)=1+loga logb n
T(n)=O(loga logb n)
Subscribe
Login
0 Comments