NICNIELIT STA 2020
October 8, 2023DatabaseManagementSystem
October 8, 2023NICNIELIT ScientistB 2020
Question 77

Consider the algorithm that solves problems of size n by recursively solving two subproblems of size n1 and then and then combining the solutions in constant time. Then the running time of the algorithm would be:
O(n)


O(logn)


O(nlogn)


O(n^{2})


O(2^{n})

Question 77 Explanation:
The given explanations are wrong.
Observe that the number of subproblems doubles n times and each subproblem uses O(1) time.
When we call two times t(n1) then it becomes T(n1)+T(n1) = 2T(n1)+1
So, the complexity is O(2^{n}).
Observe that the number of subproblems doubles n times and each subproblem uses O(1) time.
When we call two times t(n1) then it becomes T(n1)+T(n1) = 2T(n1)+1
So, the complexity is O(2^{n}).
Correct Answer: E
Question 77 Explanation:
The given explanations are wrong.
Observe that the number of subproblems doubles n times and each subproblem uses O(1) time.
When we call two times t(n1) then it becomes T(n1)+T(n1) = 2T(n1)+1
So, the complexity is O(2^{n}).
Observe that the number of subproblems doubles n times and each subproblem uses O(1) time.
When we call two times t(n1) then it becomes T(n1)+T(n1) = 2T(n1)+1
So, the complexity is O(2^{n}).
Subscribe
Login
0 Comments