CPP CPP Algorithms & Complexity Analysis 2

Question 1

Which sorting algorithm does std::stable_sort typically use?

Accepted Answer

Merge sort

Answer

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?

Accepted Answer

O(n²)

Answer

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?

Accepted Answer

std::iota

Answer

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?

Accepted Answer

Rearranges elements so those satisfying a predicate come first

Answer

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?

Accepted Answer

O(log n)

Answer

std::binary_search operates on a sorted range and repeatedly halves the search space, achieving O(log n) time complexity.

(CPP) C++ Programming Professional Certificate Practice Test