Computer Science Test 8 Nddc Scholarship

Although multiple sorting algorithms like Merge Sort and Heap Sort share the same \(O(n \log n)\) theoretical complexity, Quick Sort is often faster in practice because its hidden constant factors are 'small'. These constants represent the overhead of the operations performed within the innermost loops. Quick Sort's partitioning loop is highly efficient and works well with modern CPU architectures and cache systems, leading to a smaller constant multiplier than its competitors.

Counting Sort is a non-comparison-based sorting algorithm with a time complexity of \(O(n + k)\), where \(n\) is the number of elements and \(k\) is the range of the input values. For the algorithm to remain efficient and 'linear', \(k\) should be relatively 'small' (ideally not significantly larger than \(n\)). If \(k\) is extremely large, the auxiliary array used for counting would consume excessive memory and lead to poor performance.

Stability in sorting refers to the preservation of the relative order of records with equal keys. If two elements have the same value, a stable sort ensures that the one that appeared first in the input array will also appear first in the sorted output. This property is crucial when sorting complex data by multiple criteria, such as sorting a list of names by surname and then by first name.

Both Merge Sort and Insertion Sort are naturally stable algorithms. Insertion Sort maintains stability because it only swaps elements if they are strictly greater/smaller than the target. Merge Sort is stable provided that the 'merge' logic is written to favour the element from the left sub-array when two elements are equal. In contrast, algorithms like Quick Sort and Heap Sort are generally unstable due to their long-distance swapping mechanisms.

An in-place algorithm is one that transforms the input data without using an auxiliary data structure or 'no additional array' for storage. While a small amount of extra memory may be used for variables or the recursion stack (typically \(O(1)\) or \(O(\log n)\)), the main sorting process happens by swapping elements within the original array, making it memory-efficient.

Sorting is the process of arranging data into a logical, meaningful order. This is usually done to keep elements in 'increasing or decreasing order' (ascending or descending). Having data sorted is a prerequisite for many other efficient operations, such as performing a binary search, finding the minimum or maximum values quickly, or identifying duplicate entries within a large collection.

This is a true statement regarding the 'Prune and Search' nature of the Sieve Technique. In problems like finding the median or the \(k^{th}\) smallest element, you don't know the value of the target beforehand. You use partitioning or sieving to identify large portions of the array that definitely *cannot* contain the target and discard them, narrowing your focus until only the item of interest remains.

Computer scientists have mathematically proven a 'lower bound' for comparison-based sorting algorithms. Using decision tree models, it is proven that no comparison sort can ever be faster than \(\Omega(n \log n)\) in the worst case. This provides a theoretical baseline, confirming that algorithms like Merge Sort and Heap Sort are already achieving the best possible efficiency for comparison-based tasks.

The Sieve Technique is a classic example of 'Decrease and Conquer'. While Divide and Conquer splits a problem into several independent sub-problems (like Merge Sort), Decrease and Conquer reduces the original problem to exactly one smaller sub-problem. In the Sieve technique, a constant fraction of the data is pruned away in each step, and the search continues on the remaining single piece of data.

The Selection algorithm (such as Quickselect) works by partitioning the array in linear time \(O(n)\) and then recursing on a sub-problem of size \(n/2\) (in the ideal case). This forms a geometric series: \[ n + n/2 + n/4 + ... \] which converges to \(2n\). Therefore, the overall complexity of the algorithm is linear, denoted as \(T(n)\) or \(O(n)\).