Algorithms Space & Time Complexity Analysis 3 ā Questions and Answers
Question 1: What is the time complexity of finding the minimum element in an unsorted array of n elements?
- O(log n)
- O(1)
- O(n log n)
- O(n) (Correct answer)
Correct answer: O(n)
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?
- O(1)
- O(log n)
- O(n) (Correct answer)
- O(nĀ²)
Correct answer: O(n)
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:
- O(n log n)
- O(nĀ²)
- O(n) (Correct answer)
- O(log n)
Correct answer: O(n)
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?
- Polynomial
- Logarithmic
- Exponential
- Factorial (Correct answer)
Correct answer: Factorial
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)?
- O(nĀ² + n log n + n)
- O(nĀ² Ā· n log n Ā· n)
- O(nĀ²) (Correct answer)
- O(3nĀ²)
Correct answer: O(nĀ²)
For sequential phases, you add the complexities and then drop lower-order terms, leaving the dominant term O(nĀ²).
Question 6: What is the time complexity of a single operation on a balanced binary search tree (e.g., AVL or Red-Black tree) for search, insert, or delete?
- O(1)
- O(n)
- O(log n) (Correct answer)
- O(n log n)
Correct answer: O(log n)
A balanced BST maintains height O(log n), so any search, insert, or delete traverses at most O(log n) nodes.
Question 7: Which of the following sorting algorithms achieves O(n) time complexity under specific conditions (e.g., limited integer range)?
- Heapsort
- Merge sort
- Counting sort (Correct answer)
- Quicksort
Correct answer: Counting sort
Counting sort runs in O(n + k) where k is the range of input values; when k = O(n), this simplifies to O(n), bypassing the comparison-based O(n log n) lower bound.
Algorithms Space & Time Complexity Analysis 3
What is the time complexity of finding the minimum element in an unsorted array of n elements?