CCP Sorting, Searching & Big-O 2

Question 1

Which sorting algorithm has O(n log n) worst-case time complexity?

Accepted Answer

Merge Sort

Answer

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?

Accepted Answer

O(1)

Answer

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?

Accepted Answer

O(2ⁿ)

Answer

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?

Accepted Answer

Binary Heap

Answer

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?

Accepted Answer

O(n log n)

Answer

On average, Quick Sort partitions the array roughly in half each time, yielding O(n log n) average performance.

(CCP) Certified Computing Professional Practice Test