CPP CPP Algorithms & Complexity Analysis 2 — Questions and Answers
Question 1: Which sorting algorithm does std::stable_sort typically use?
- Quicksort
- Heapsort
- Merge sort (Correct answer)
- Insertion sort
Correct answer: Merge sort
std::stable_sort typically uses merge sort to preserve the relative order of equal elements with O(n log n) complexity.
Question 2: What is the worst-case time complexity of quicksort?
- O(n log n)
- O(n)
- O(n²) (Correct answer)
- O(log n)
Correct answer: O(n²)
Quicksort degrades to O(n²) in the worst case when the pivot always creates maximally unbalanced partitions, such as on already-sorted input.
Question 3: Which C++ algorithm fills a range with sequentially increasing values?
- std::fill
- std::generate
- std::iota (Correct answer)
- std::transform
Correct answer: std::iota
std::iota fills a range with sequentially increasing values starting from an initial value and is defined in <numeric>.
Question 4: What does std::partition do to a range?
- Divides a container into two equal halves
- Rearranges elements so those satisfying a predicate come first (Correct answer)
- Sorts elements by a partition key
- Splits a string by delimiter
Correct answer: Rearranges elements so those satisfying a predicate come first
std::partition rearranges elements so all elements satisfying the predicate appear before those that do not.
Question 5: What is the time complexity of std::binary_search on a sorted range?
- O(n)
- O(1)
- O(log n) (Correct answer)
- O(n log n)
Correct answer: O(log n)
std::binary_search operates on a sorted range and repeatedly halves the search space, achieving O(log n) time complexity.
Question 6: Which <numeric> algorithm computes the sum of a range sequentially from left to right?
- std::count
- std::accumulate (Correct answer)
- std::reduce
- std::transform_reduce
Correct answer: std::accumulate
std::accumulate from <numeric> folds a range from left to right using a binary operation, defaulting to addition.
CPP CPP Algorithms & Complexity Analysis 2
Which sorting algorithm does std::stable_sort typically use?