Design Algorithm Analysis GATE previous year questions with answer

Given:
Input sequence is already sorted in ascending order.
Four statements about running times of Quicksort, Bubblesort, Mergesort, and Insertion sort.
To find:
Which of the statements are TRUE.
Solution:
Let me check each statement one by one for an already sorted input.
First, looking at statement I (Quicksort):
In standard Quicksort, the pivot is usually chosen as the first or the last element.
When the array is already sorted, this choice produces the most unbalanced partition possible, of sizes 0 and n - 1.
So the recurrence relation becomes:
T(n) = T(n - 1) + Θ(n)
Solving this recurrence gives:
T(n) = Θ(n²)
So statement I is TRUE.
Now, checking statement II (Bubblesort):
An optimized Bubblesort uses a flag to detect if any swap occurred during a pass.
Since the array is already sorted, no swaps occur in the very first pass of n - 1 comparisons, and the algorithm terminates immediately.
So the running time is Θ(n), not Θ(n²).
Thus, statement II is FALSE.
Next, checking statement III (Mergesort):
Mergesort always divides the list into two equal halves irrespective of the input order.
Its recurrence relation is always:
T(n) = 2T(n/2) + Θ(n)
Solving this always yields Θ(n log n) time in all cases.
So statement III is FALSE.
Finally, checking statement IV (Insertion sort):
For an already sorted array, each element is compared only once with its predecessor and no shifts are needed.
So the inner loop runs in O(1) time for every element.
The total number of comparisons is simply n - 1, which gives a running time of Θ(n).
So statement IV is TRUE.
Therefore, statements I and IV are TRUE.
Answer:
(D) I and IV only

Given:
Three sorting algorithms: Insertion sort, Merge sort, and Quick sort.
To find:
The worst case running times of Insertion sort, Merge sort, and Quick sort, respectively.
Solution:
Let me analyze the worst case running time for each algorithm one by one.
First, consider Insertion sort.
In the worst case, the input array is reverse sorted.
For each element at index i, we have to make i comparisons and shifts.
Total work done is proportional to 1 + 2 + 3 + ... + (n - 1) = (n(n - 1))/2, which gives Θ(n²).
Next, consider Merge sort.
Merge sort divides the array into two halves, sorts them recursively, and merges them in linear time.
The recurrence relation is T(n) = 2T(n/2) + Θ(n).
Solving this recurrence using Master theorem gives T(n) = Θ(n log n) in all cases, including the worst case.
Now, consider Quick sort.
The worst case occurs when the chosen pivot always partitions the array into two subproblems of sizes 0 and n - 1.
This happens, for instance, when the array is already sorted and we pick the first or last element as the pivot.
The recurrence becomes T(n) = T(n - 1) + Θ(n).
Solving this gives T(n) = Θ(n²).
So, combining all three in order, the worst case times are Θ(n²), Θ(n log n), and Θ(n²).
Checking the options, this matches with option D.
Answer: (D) Θ(n²), Θ(n log n) and Θ(n²)

PROCESSED

PROCESSED

PROCESSED

The question asks us to compare the number of comparisons made by QuickSort when the first element is always chosen as the pivot.
Analyze the Options:
Input 1: [1, 2, 3, 4, 5]
The first element, 1, is the smallest element, so every other element is compared with the pivot. This creates the worst-case pattern, where the list is divided as 0 and 4, then 0 and 3, and so on.
Comparisons = 4 + 3 + 2 + 1 = 10.
Input 2: [4, 1, 5, 3, 2]
The first pivot is 4. The elements 1, 3, and 2 go to the left, while 5 goes to the right. The resulting subarrays are smaller and require fewer comparisons than the first input.
Comparisons = 4 + 3 + 1 = 8.
Comparison:
t₁ = 10 and t₂ = 8.
Therefore, t₁ > t₂.
Correct Answer: c) t1 > t2