GATE CS 2017 (Afternoon) — Question 3

AlgorithmsAsymptotic Analysis (O, Omega, Theta Complexities)MCQ1 mark · −1/3 if wrongEasy

Match the algorithms with their time complexities: List-I (Algorithm) (P) Towers of Hanoi with n disks (Q) Binary search given n sorted numbers (R) Heap sort given n numbers at the worst case (S) Addition of two \(n \times n\) matrices List-II (Time complexity) (i) \(\Theta(n^2)\) (ii) \(\Theta(n \log n)\) (iii) \(\Theta(2^n)\) (iv) \(\Theta(\log n)\)
  1. A
    P - (iii), Q - (iv), R - (i), S - (ii)
  2. B
    P - (iv), Q - (iii), R - (i), S - (ii)
  3. C
    P - (iii), Q - (iv), R - (ii), S - (i)
  4. D
    P - (iv), Q - (iii), R - (ii), S - (i)
Practise the full 2017-AN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAPractise this subject in the exam simulatorTimed, GATE-style tests with analytics that find your weak topics.
Practise more on Asymptotic Analysis (O, Omega, Theta Complexities)Timed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group