###### NIC-NIELIT STA 2020

October 8, 2023###### Database-Management-System

October 8, 2023# NIC-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(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(n-1) then it becomes T(n-1)+T(n-1) = 2T(n-1)+1

So, the complexity is O(2Observe 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(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(n-1) then it becomes T(n-1)+T(n-1) = 2T(n-1)+1

So, the complexity is O(2Observe 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(2

^{n}). Subscribe

Login

0 Comments