CCP Sorting, Searching & Big-O 3

Question 1

What is the worst-case time complexity of searching an unsorted array of n elements?

Accepted Answer

O(n)

Answer

Linear search must examine every element in the worst case when the target is absent or at the last position.

Question 2

Which sorting algorithm is most efficient when the input data is nearly sorted?

Accepted Answer

Insertion Sort

Answer

Insertion Sort performs O(n) comparisons on nearly sorted data because each element moves only a short distance.

Question 3

The Master Theorem is used to analyze the time complexity of:

Accepted Answer

Divide-and-conquer recurrences

Answer

The Master Theorem provides a formula for solving recurrences of the form T(n) = aT(n/b) + f(n) common in divide-and-conquer algorithms.

Question 4

Which of the following describes a stable sorting algorithm?

Accepted Answer

Equal elements maintain their original relative order

Answer

A stable sort preserves the relative order of elements with equal keys, which matters when sorting by multiple criteria.

Question 5

What is the time complexity of building a max-heap from an unsorted array of n elements?

Accepted Answer

O(n)

Answer

Using the bottom-up heapify approach, a heap can be built in O(n) time despite each heapify call being O(log n).

(CCP) Certified Computing Professional Practice Test