Algorithms sort in ascending order. On an already ascending input, which are true? I: Quicksort takes (n2). II: Bubblesort takes (n2). III: Mergesort takes (n). IV: Insertion sort takes (n).

GATE 2016 CS (CS2) – Question 23

Algorithms · Searching, Sorting and Hashing · 1 mark · Multiple choice

Algorithms sort in ascending order. On an already ascending input, which are true? I: Quicksort takes $\Theta(n^2)$. II: Bubblesort takes $\Theta(n^2)$. III: Mergesort takes $\Theta(n)$. IV: Insertion sort takes $\Theta(n)$.

I and II only
I and III only
II and IV only
I and IV only

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) I and IV only

Explanation

The keyed D assumes first/last-element-pivot quicksort and early-termination bubble sort. Quicksort then repeatedly splits into 0 and n−1, costing Θ(n²). Bubble sort stops after one no-swap pass. Ordinary mergesort is Θ(n log n), and insertion sort makes one comparison per new item, Θ(n). Thus I and IV under those conventions. The unspecified pivot and bubble-sort variant make the printed question implementation-dependent.

More Searching, Sorting and Hashing questions

GATE 2013 CS (CS1) Q16 – What is the tightest upper bound on swaps used by selection sort on n numbers?
GATE 2010 CS (CS1) Q62 – A ten-slot hash table uses h(k)=k mod 10 and linear probing. Its occupied slots are 2:42,…
GATE 2010 CS (CS1) Q63 – A ten-slot hash table uses h(k)=k mod 10 and linear probing. Its occupied slots are 2:42,…
GATE 2015 CS (CS2) Q50 – Which integer hash function distributes keys i=0,…,2020 most uniformly over buckets 0,…,9?
GATE 2015 CS (CS3) Q22 – A hash table with 25 slots stores 2000 elements. Find its load factor α.
GATE 2021 CS (CS2) Q18 – Find the worst-case number of arithmetic operations in recursive binary search on a sorted…

All Searching, Sorting and Hashing questions →