Searching and Sorting : MCQs & PYQs with Explanation

Option C

Selection sort is a sorting algorithm in which the smallest element is repeatedly selected from the unsorted part of the array and placed at its correct position. 
For n elements, the algorithm performs comparisons approximately equal to [n(n−1)]/2. Since the dominant term is n², the time complexity of selection sort is O(n²).

Option A

The given array state is {25, 75, 95, 125, 80, 5, 10}. This indicates that the first four elements are already sorted, and insertion sort will now continue with the remaining elements.
First, 80 is inserted into the sorted part {25, 75, 95, 125}. It is compared with 125, 95, and 75 before being placed in its correct position. This takes 3 comparisons. The array becomes {25, 75, 80, 95, 125, 5, 10}.
Next, 5 is inserted. It is compared with 125, 95, 80, 75, and 25 before reaching the beginning of the array. This requires 5 comparisons. The array becomes {5, 25, 75, 80, 95, 125, 10}.
Finally, 10 is inserted. It is compared with 125, 95, 80, 75, 25, and then with 5 before being placed correctly. This takes 6 comparisons.
So,
For 80, 3 comparisons.
For 5, 5 comparisons.
For 10, 6 comparisons.
Therefore, total comparison, 3+5+6 =14.

Option D

The best-case time complexity of Quick Sort occurs when the pivot divides the array into two equal halves at every recursive step.

Option C

In Insertion Sort, the array is conceptually divided into two parts:

• Sorted Portion (Left Side)
• Unsorted Portion (Right Side)

During each iteration, the algorithm takes the next element from the unsorted part and inserts it into its correct position within the sorted part by shifting larger elements to the right.
Thus, after the Kth iteration, the first (K+1) elements become sorted.
Array Initially:
10, 5, 16, 2, 8, 9
Iteration 1:
Insert 5 into the sorted portion [10].
5, 10, 16, 2, 8, 9
Now first 2 elements are sorted.
Iteration 2:
Insert 16 into the sorted portion [5, 10].
Since 16 is larger than both, it stays at the end.
5, 10, 16, 2, 8, 9
Now first 3 elements are sorted.
Iteration 3:
Insert 2 into the sorted portion [5, 10, 16].
All elements shift right.
2, 5, 10, 16, 8, 9
This exactly matches the array given in the question after three iterations.

Option C

Quicksort is a popular sorting algorithm used to arrange elements in ascending or descending order. It is based on the Divide and Conquer technique.
In Divide and Conquer:

• The problem is divided into smaller subproblems.
• Each subproblem is solved separately.
• The solutions are combined to get the final result.

Option A

To arrange in increasing order, we compare time complexities of the given algorithms. Binary Search has time complexity O(log n), Merge Sort has O(n log n), and Bubble Sort has O(n²).
Since log n < n log n < n², the increasing order is Binary Search → Merge Sort → Bubble Sort.

Option A

A recurrence relation is an equation that expresses the running time of a problem in terms of smaller instances of the same problem. It is used in the analysis of recursive algorithms because recursion naturally breaks a large problem into smaller subproblems.

By writing and solving the recurrence relation, we can calculate the overall time complexity of the algorithm in an exact and systematic way.

In the best case of Quick Sort, each partition splits the array into two equal halves. The partitioning step itself requires scanning the entire array once, which takes Θ(n) time. After this step, two recursive calls are made on subarrays of size n/2 each, giving 2T(n/2). Therefore, the recurrence relation can be expressed as T(n) = 2T(n/2) + Θ(n). By applying the Master Theorem to this recurrence, we find that the solution is T(n) = Θ(n log n).

Option D

Binary search works only on a sorted list. It repeatedly divides the search space into halves, giving a time complexity of O(log₂ n). In an unsorted list, binary search cannot be applied.

Option D

The worst-case time complexity of Selection Sort is O(n²). This is because, in every pass of the algorithm, the smallest (if sort in ascending order) or largest (if sort in descending order) element is selected from the unsorted portion of the array by scanning all remaining elements. This requires (n−1) comparisons in the first pass, (n−2) in the second pass, and so on, until only one element is left.
The total number of comparisons becomes (n−1)+(n−2)+...+1=n(n−1)/2, which simplifies to O(n²).

Option A

The input array is 32, 51, 27, 85, 66, 23, 13, 57. In bubble sort, we compare adjacent elements and swap them if the left element is greater than the right. During the first pass, the largest element moves to the last position.

During first pass, compare 32 and 51 → no swap, 51 and 27 → swap, 51 and 85 → no swap, 85 and 66 → swap, 85 and 23 → swap, 85 and 13 → swap, and 85 and 57 → swap. After completing these comparisons and swaps, the array becomes 32, 27, 51, 66, 23, 13, 57, 85.

Option B

Binary search works only on a sorted array and repeatedly divides the search space into half. In each step, it compares the target element with the middle element and eliminates one half of the array. 
Since the number of elements is reduced by half every time, the number of steps required grows logarithmically with respect to N. Therefore, the time complexity of binary search in the worst case is O(log N).

Option B

In Sequential or Linear Search, elements are checked one by one from the beginning until the required element is found. If the search is successful, the element may be located at any position from the first to the last, and each position is equally likely. Therefore, the number of comparisons required can be 1, 2, 3, … up to n.
To find the average number of comparisons, we take the mean of all possible cases:
(1+2+ ... +n)/n = [n(n+1)/2]/n = (n+1)/2.
Thus, the average successful search time in sequential search is (n+1)/2.

Option A

Time complexity tells us how much time an algorithm takes with respect to input size n. In linear search, we check elements one by one.
In the worst case, when the element is at the last position or not present, we need to check all n elements, so the time complexity becomes O(n).

• The best case of linear search is when the element is found at the first position, which is O(1).
• The best case of binary search is also O(1).
• Worst case of binary search is O(log n).
   

Option C

Binary Search works on the principle of repeatedly dividing the search space into halves. For this method to work correctly, the elements must be sorted. The order of sorting can be either ascending or descending.

Option B

Binary Search is an efficient search algorithm that works on the principle of divide and conquer:

• It assumes the array is Sorted in ascending or descending order.
• It compares the target value with the middle element of the array.
  • If equal then item is found.
  • If smaller then search the left half.
  • If larger then search the right half.

With each comparison, half of the array is eliminated, making the search faster than Linear Search.