NIC-NIELIT STA 2020
October 8, 2023Database-Management-System
October 8, 2023NIC-NIELIT Scientist-B 2020
| Question 77 |
Consider the algorithm that solves problems of size n by recursively solving two subproblems of size n-1 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(n2) | |
| O(2n) |
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(n-1) then it becomes T(n-1)+T(n-1) = 2T(n-1)+1
So, the complexity is O(2n).
Observe that the number of subproblems doubles n times and each subproblem uses O(1) time.
When we call two times t(n-1) then it becomes T(n-1)+T(n-1) = 2T(n-1)+1
So, the complexity is O(2n).
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(n-1) then it becomes T(n-1)+T(n-1) = 2T(n-1)+1
So, the complexity is O(2n).
Observe that the number of subproblems doubles n times and each subproblem uses O(1) time.
When we call two times t(n-1) then it becomes T(n-1)+T(n-1) = 2T(n-1)+1
So, the complexity is O(2n).
Subscribe
Login
0 Comments