Time Left - 10:00 mins

GATE CS 2018 - Algorithms Quiz 4 (Divide & Conquer-2)

Attempt now to get your rank among 512 students!

Question 1

The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is

Question 2

Consider the polynomial

The minimum number of multiplications needed to evaluate p on an input x is:

Question 3

In quick sort, for sorting n elements, the (n/4)^th smallest element is selected as pivot using an O(n) time algorithm.
What is the worst case time complexity of the quicksort?

Question 4

A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is?

Question 5

What is the time complexity for counting the inversion pairs in an array size of n, using merge sort?

512 attempts
1 upvote
20 comments

Tags :

GATE & PSU CS Algorithms

Jan 13GATE & PSU CS