CS Free MCQ Bank

[ 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 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 ]

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 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.

[ Option A ]

Merge Sort is a classic example of the divide-and-conquer algorithm. It works by dividing the array into two halves, recursively sorting each half, and then combining or merging the sorted halves.

LIST OF PROBLEMS THAT SOLVED USING DIVIDE AND CONQUER APPROACH:

[ Option B ]

Merge Sort is an example of the Divide and Conquer algorithm design paradigm. It works by repeatedly dividing the array into two halves, conquering each half by sorting them, and then combining the two sorted halves into one sorted array.

[ Option A ]

Must Know:

• A sorting algorithm is called stable if it preserves the relative order of equal elements in the sorted output. For example, suppose we have a list of students with (Name, Marks) as, (Ramesh, 90), (Salman, 80), (Mahesh, 90). If we sort them by Marks, a stable sort will keep (Ramesh, 90) before (Mahesh, 90) in the result, since Ramesh appeared before Mahesh in the original list.
• Space Complexity tells us how much extra memory the algorithm needs apart from the input data.
• O(1) Space Complexity : Means the algorithm uses constant extra space, no matter how big the input. So, O(1) is very memory efficient, uses only a few extra variables.
• O(n) Space Complexity : Means the algorithm uses extra space proportional to the input size. So, O(n) uses extra memory, creates new arrays or data structures.

[ Option C ]

Statement I says that binary search is faster than linear search. This is true because binary search works by repeatedly dividing the sorted list in half, giving it a time complexity of O(log n), whereas linear search checks each element one by one and takes O(n) time.

Statement II says that binary search may not be applied on all the input lists on which linear search can be applied. This is also true because binary search requires the list to be sorted, while linear search works on both sorted and unsorted lists.

[ Option D ]

Binary Search is an efficient searching algorithm used only on sorted lists or arrays. The key idea behind binary search is that instead of checking every element one by one, it repeatedly divides the search range into two halves.  At each step, it compares the target value with the middle element. 
If the target is equal to the middle value, the search ends. If the target is smaller, the search continues in the left half, and if it is larger, the search continues in the right half.
Because the size of the search interval becomes half at every step, the time complexity is O(log N).

[ Option C ]