Sorting, Searching & Big-O Flashcards
7 cards from real CCP practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.
Read the first 7 Sorting, Searching & Big-O flashcards as text
Which sorting algorithm has O(n log n) worst-case time complexity?
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.
What is the space complexity of an in-place sorting algorithm?
Answer: O(1)
In-place algorithms use only a constant amount of extra memory (O(1)) beyond the input array itself.
In Big-O notation, which of the following grows fastest as n increases?
Answer: O(2ⁿ)
Exponential O(2ⁿ) grows faster than any polynomial function, including O(n³), as n becomes large.
Which data structure is most commonly used to implement an efficient priority queue for heap sort?
Answer: Binary Heap
A binary heap supports O(log n) insertion and extraction, making it ideal for heap sort and priority queues.
What is the average-case time complexity of Quick Sort?
Answer: O(n log n)
On average, Quick Sort partitions the array roughly in half each time, yielding O(n log n) average performance.
Binary search requires the input array to be:
Answer: Sorted (ascending or descending)
Binary search works on any sorted order—ascending or descending—as long as the comparison direction is adjusted accordingly.
Which term describes an algorithm whose running time does not depend on input size?
Answer: O(1)
O(1) or constant time means execution takes the same amount of time regardless of input size.