Question
a.
T (n) = 2T (n - 2) + 2
b.
T (n) = 2T (n - 1) + n
c.
T (n) = 2T (n/2) + 1
d.
T (n) = 2T (n - 1) + 1
Posted under GATE cse question paper Data Structures and Algorithms
Engage with the Community - Add Your Comment
Confused About the Answer? Ask for Details Here.
Know the Explanation? Add it Here.
Q. The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is
Similar Questions
Discover Related MCQs
Q. Which of the following statements are TRUE?
(1) The problem of determining whether there exists a cycle in an undirected graph is in P.
(2) The problem of determining whether there exists a cycle in an undirected graph is in NP.
(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.
View solution
Q. The best case time complexity for a successful binary search is O(1). Similarly the best case time complexity for an unsuccessful binary search is…….
View solution
Q. State the worst case time complexity for quick sort.
View solution
Q. A search technique where we keep expanding nodes with least accumulated cost so far is called
View solution
Q. Both P and NP are closed under the operation of
View solution
Q. In general, Amortization is used for specific types of algorithms like
View solution
Q. The Single Source Shortest path algorithm takes……..time.
View solution
Q. Time required to find an element at level i of a tree is
View solution
Q. What are the number of spanning trees possible from a graph containing n vertices?
View solution
Q. The best average behavior is shown by
View solution
Q. Divide and Conquer is an important algorithm design paradigm based on
View solution
Q. What is the time complexity for printing a list of n items to the screen, looking at each item once?
View solution
Q. What is the time complexity for taking a list of n items, and comparing every item to every other item?
View solution
Q. The knapsack problem is also called as…….problem.
View solution
Q. What is the (exact) solution to the travelling salesman problem using dynamic programming (c>1), where c is any constant?
View solution
Q. The time complexity for solving the traveling salesman problem via brute-force search takes
View solution
Q. The time complexity for finding an item in a sorted array using binary search is
View solution
Q. The time complexity of determining a number is odd or even is
View solution
Q. The worst case of the job sequencing with deadline is
View solution
Q. The postfix expression for the infix expression (A+B*(C+D))/ (F+D*E) is
View solution
Suggested Topics
Are you eager to expand your knowledge beyond Data Structures and Algorithms? We've curated a selection of related categories that you might find intriguing.
Click on the categories below to discover a wealth of MCQs and enrich your understanding of Computer Science. Happy exploring!
