CCP Sorting, Searching & Big-O 2 — Questions and Answers
Question 1: Which sorting algorithm has O(n log n) worst-case time complexity?
- Quick Sort
- Merge Sort (Correct answer)
- Bubble Sort
- Insertion Sort
Correct answer: Merge Sort
Merge Sort guarantees O(n log n) in all cases by dividing and merging, unlike Quick Sort which degrades to O(n²) in the worst case.
Question 2: What is the space complexity of an in-place sorting algorithm?
- O(n)
- O(log n)
- O(1) (Correct answer)
- O(n²)
Correct answer: O(1)
In-place algorithms use only a constant amount of extra memory (O(1)) beyond the input array itself.
Question 3: In Big-O notation, which of the following grows fastest as n increases?
- O(n log n)
- O(n²)
- O(2ⁿ) (Correct answer)
- O(n³)
Correct answer: O(2ⁿ)
Exponential O(2ⁿ) grows faster than any polynomial function, including O(n³), as n becomes large.
Question 4: Which data structure is most commonly used to implement an efficient priority queue for heap sort?
- Binary Search Tree
- Stack
- Binary Heap (Correct answer)
- Hash Table
Correct answer: Binary Heap
A binary heap supports O(log n) insertion and extraction, making it ideal for heap sort and priority queues.
Question 5: What is the average-case time complexity of Quick Sort?
- O(n²)
- O(n)
- O(n log n) (Correct answer)
- O(log n)
Correct answer: O(n log n)
On average, Quick Sort partitions the array roughly in half each time, yielding O(n log n) average performance.
Question 6: Binary search requires the input array to be:
- Sorted in ascending order only
- Randomly ordered
- Sorted (ascending or descending) (Correct answer)
- Stored in a linked list
Correct answer: Sorted (ascending or descending)
Binary search works on any sorted order—ascending or descending—as long as the comparison direction is adjusted accordingly.
Question 7: Which term describes an algorithm whose running time does not depend on input size?
- O(log n)
- O(n)
- O(1) (Correct answer)
- O(n log n)
Correct answer: O(1)
O(1) or constant time means execution takes the same amount of time regardless of input size.
CCP Sorting, Searching & Big-O 2
Which sorting algorithm has O(n log n) worst-case time complexity?