Question 6864 – Algorithms
November 26, 2023UGC NET June-2019 CS Paper-2
November 26, 2023Question 6923 – Algorithms
The solution of the recurrence relation
Correct Answer: B
Question 350 Explanation:
Assume T(n) = O(1) for small n≤80.
T(n) ≤ T(n/5)+T((7n/10)+6)+O(n)
Inductively verify that T(n)≤cn for some constant c.
T(n) ≤ c(n/5)+c(7n/10+6)+O(n)
≤ 9cn/10+6c+O(n)
≤ cn
In above, choose c so that c((n/10)−6) beats the function O(n) for all n.
Note: They given ‘s’ instead 5.
T(n) ≤ T(n/5)+T((7n/10)+6)+O(n)
Inductively verify that T(n)≤cn for some constant c.
T(n) ≤ c(n/5)+c(7n/10+6)+O(n)
≤ 9cn/10+6c+O(n)
≤ cn
In above, choose c so that c((n/10)−6) beats the function O(n) for all n.
Note: They given ‘s’ instead 5.
O(lg n)
O(n)
O(n lg n)
None of the above
Subscribe
Login
0 Comments