Which of the following describes the space complexity of counting sort?
O(n + k), where k is the range of input values
O(n)
O(1)
O(log n)
Which of the following real-world applications is well-suited for counting sort?
Sorting an array of timestamps representing events in chronological order.
Sorting a list of words alphabetically.
Sorting a large dataset of student GPAs ranging from 0.0 to 4.0.
Sorting a collection of images based on their file sizes.
Why is binary search a preferred algorithm for searching in sorted arrays compared to linear search?
Binary search uses less memory than linear search.
Binary search is easier to implement and understand than linear search.
Binary search works correctly even on unsorted arrays, while linear search does not.
Binary search has a time complexity of O(log n), which is significantly faster than linear search's O(n) complexity for large datasets.
What is the worst-case time complexity of Merge Sort?
O(n log n)
O(n^2)
In which scenario is Bucket Sort likely to perform poorly?
Data is heavily skewed towards one end of the range
Data is already sorted in reverse order
Data is uniformly distributed within a known range
Data consists of a small number of unique elements
What is the worst-case time complexity of Heap Sort?
What is a key characteristic of in-place partitioning within the context of Quick Sort?
In-place partitioning is only applicable when the input array is already sorted in reverse order.
The partitioning process is performed entirely within the original array, without requiring the allocation of substantial additional memory proportional to the input size.
The partitioning step always selects the first element of the subarray as the pivot.
The algorithm sorts the array by recursively dividing it into smaller subarrays and then merging them back together.
Which aspect of Radix Sort's implementation significantly impacts its overall performance, particularly for large datasets?
Data structure used to store and access buckets
Choice of sorting algorithm for individual digits
Initial order of elements in the input array
Number of passes required to sort all digits
Which of the following best describes the heap property in a binary heap used for Heap Sort?
The left and right subtrees are sorted
The heap is always a complete binary tree
Each node is smaller than or equal to its children
Each node is greater than or equal to its children
Bucket Sort achieves its efficiency by:
Recursively dividing the input into smaller subproblems
Distributing elements into buckets based on their range
Using a priority queue to maintain sorted order during insertion
Exploiting the relative order of elements within the input