Exams › GATE › Technical
The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
- Θ(n log n), Θ(n log n), and Θ(n²)
- Θ(n²), Θ(n²), and Θ(n log n)
- Θ(n²), Θ(n log n), and Θ(n log n)
- Θ(n²), Θ(n log n), and Θ(n²)
Correct answer: Θ(n²), Θ(n log n), and Θ(n²)
Solution
Insertion sort has a worst-case running time of Θ(n²) due to its nested loops when the input is in reverse order. Merge sort consistently performs at Θ(n log n) because it divides the array and merges sorted subarrays regardless of the input order. Quick sort, while efficient on average, can degrade to Θ(n²) in the worst case when the pivot selection is poor, such as when the smallest or largest element is consistently chosen.
Related GATE Technical questions
- We want to design a synchronous counter that counts the sequence 0-1-0-2-0-3 and then repeats. The minimum number of J-K flip-flops required to implement this counter is
- A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?
- Consider the following C program.
void f(int, short);
void main()
{
int i = 100;
short s = 12;
short *p = &s;
________; // call to f()
}
Which one of the following expressions, when placed in the blank above, will NOT result in a type checking error?
- Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?
P: Minimum spanning tree of G does not change
Q: Shortest path between any pair of vertices does not change
- Consider the following C program.
#include<stdio.h>
void mystery(int *ptra, int *ptrb) {
int *temp;
temp = ptrb;
ptrb = ptra;
ptra = temp;
}
int main() {
int a=2016, b=0, c=4, d=42;
mystery(&a, &b);
if (a < c)
mystery(&c, &a);
mystery(&a, &d);
printf("%d
", a);
}
The output of the program is _________.
- Which of the following languages is generated by the given grammar?
S → aS | bS | ε
⚔️ Practice GATE Technical free + battle 1v1 →