Computer Science Test 8 Nddc Scholarship

The Sieve Technique is often categorized as 'Decrease and Conquer'. While 'Divide and Conquer' splits a problem into multiple sub-problems, Decrease and Conquer reduces the original problem to a single smaller sub-problem. The Sieve technique is the 'Prune and Search' variation of this, where we prune a constant fraction of the input in each step, making it a distinct and highly effective strategy for selection and optimization problems.

In a binary tree, the number of nodes at any level \(i\) is \(2^i\). In a complete (full) binary tree, every level is filled. The total number of nodes is the sum of a geometric progression from level 0 to level \(h\):\[ \sum_{i=0}^{h} 2^i = 2^{h+1} - 1 \] For example, a tree of height 2 has \(2^{2+1} - 1 = 7\) nodes (1 at root, 2 at level 1, 4 at level 2).

The Sieve Technique is designed for 'selection' problems where the goal is to pinpoint one specific element (like the median or the smallest value) out of a collection of '\(n\) items'. By using a strategy to identify and discard large groups of items that are guaranteed not to be the target, the algorithm narrows down the search space until only the single desired item remains.

Memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. In recursion, many problems (like the Fibonacci sequence) recalculate the same values thousands of times. Memoization 'remembers' the result of each recursive call by writing it in a table (usually an array or hash map), effectively turning an exponential-time problem into a linear-time one.

While \(O(n \log n)\) is the fastest complexity for comparison-based sorts (like Mergesort), algorithms that use non-comparison methods—such as Counting Sort—can achieve a complexity of \(O(n + k)\), where \(k\) is the range of the input. In cases where \(k\) is relatively small, \(O(n + k)\) is theoretically faster as it is linear, outperforming even the highly efficient \(O(n \log n)\) algorithms.

Quick Sort is known as an 'in-place' algorithm because it requires only a small, constant amount of extra storage space beyond the initial array (specifically for the recursion stack). However, it is 'not stable'. A stable sort preserves the relative order of equal elements; because Quick Sort partitions elements by swapping them across long distances relative to a pivot, it frequently changes the relative order of identical elements.

Quick Sort is the quintessential example of an in-place but unstable sorting algorithm. It sorts by partitioning the array around a pivot, using swaps to move elements to their correct side. These swaps can jump equal elements over each other, destroying their original relative order. In contrast, Merge Sort is stable but not in-place (requires extra memory), and Bubble Sort is both stable and in-place but very slow.

An 'in-place' algorithm is one that transforms input using no auxiliary data structure. Although a small amount of extra storage is allowed for auxiliary variables (typically \(O(1)\) or \(O(\log n)\) for the recursion stack), the algorithm does not require an 'additional array' to hold a copy of the data. This makes in-place algorithms like Quick Sort or Heap Sort highly memory-efficient compared to algorithms like Merge Sort, which requires an entirely separate array to perform the merging process.

While \(O(n \log n)\) is the fastest possible time complexity for comparison-based sorting algorithms, non-comparison sorts like Counting Sort can achieve a linear time complexity of \(O(n + k)\). In scenarios where the range of input values (\(k\)) is not significantly larger than the number of elements (\(n\)), \(O(n + k)\) is mathematically faster than \(O(n \log n)\) because it does not involve the logarithmic factor required by comparisons.

The performance of Quick Sort is dictated by how evenly the 'pivot elements' partition the array. If a pivot consistently splits the array into two nearly equal halves, the algorithm achieves its best-case complexity of \(O(n \log n)\). However, if the pivot selection is poor (e.g., always picking the smallest or largest element in an already sorted array), the partitions become highly unbalanced, causing the algorithm to degrade to its worst-case performance of \(O(n^2)\).