Algorithms Space & Time Complexity Analysis 3

Question 1

What is the time complexity of finding the minimum element in an unsorted array of n elements?

Accepted Answer

O(n)

Answer

Without any ordering, every element must be examined at least once, requiring O(n) comparisons.

Question 2

Which of the following best describes the space complexity of an iterative (non-recursive) merge sort?

Accepted Answer

O(n)

Answer

Merge sort requires an auxiliary array of size n to hold merged results, giving O(n) space complexity regardless of iterative or recursive implementation.

Question 3

The time complexity of building a binary heap from an unsorted array using the heapify-down approach is:

Accepted Answer

O(n)

Answer

The standard linear-time heap construction performs at most 2n comparisons total due to the geometric series of work at each level.

Question 4

An algorithm is described as O(n!) in time complexity. What category does this fall into?

Accepted Answer

Factorial

Answer

O(n!) is factorial complexity, which grows even faster than exponential (e.g., O(2ⁿ)) and is seen in brute-force permutation problems.

Question 5

When analyzing an algorithm with multiple independent phases that run sequentially, what is the overall time complexity if the phases are O(n²), O(n log n), and O(n)?

Accepted Answer

O(n²)

Answer

For sequential phases, you add the complexities and then drop lower-order terms, leaving the dominant term O(n²).

Algorithms Practice Test

Algorithms Practice Test

Algorithms Space & Time Complexity Analysis 3