CS Free MCQ Bank

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

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