Algorithms Space & Time Complexity Analysis 2 — Questions and Answers
Question 1: What is the amortized time complexity of a single push operation on a dynamic array that doubles in size when full?
- O(n)
- O(log n)
- O(n²)
- O(1) (Correct answer)
Correct answer: O(1)
Although occasional resize operations cost O(n), the cost is spread across all pushes, making the amortized per-push cost O(1).
Question 2: A recursive Fibonacci function fib(n) = fib(n-1) + fib(n-2) without memoization has which time complexity?
- O(n)
- O(n log n)
- O(2ⁿ) (Correct answer)
- O(n²)
Correct answer: O(2ⁿ)
Each call spawns two sub-calls, creating an exponential call tree with approximately 2ⁿ nodes.
Question 3: Which notation describes the best-case lower bound on an algorithm's running time?
- Big-O (O)
- Big-Theta (Θ)
- Big-Omega (Ω) (Correct answer)
- Little-o (o)
Correct answer: Big-Omega (Ω)
Big-Omega (Ω) provides an asymptotic lower bound, meaning the algorithm takes at least that long in the best case.
Question 4: What is the space complexity of a recursive depth-first search (DFS) on a graph with V vertices and E edges?
- O(V + E)
- O(E)
- O(V) (Correct answer)
- O(1)
Correct answer: O(V)
DFS uses the call stack, which in the worst case holds up to V frames (one per vertex on the deepest path), giving O(V) space.
Question 5: Quicksort has an average-case time complexity of O(n log n). What is its worst-case time complexity?
- O(n log n)
- O(n²) (Correct answer)
- O(n)
- O(log n)
Correct answer: O(n²)
When the pivot is always the smallest or largest element (e.g., sorted input with naïve pivot selection), partitioning is unbalanced and degrades to O(n²).
Question 6: If an algorithm runs in O(n log n) time, which of the following input sizes would see the greatest relative slowdown compared to O(n)?
- n = 10
- n = 100
- n = 1,000
- n = 1,000,000 (Correct answer)
Correct answer: n = 1,000,000
The log n factor grows with n, so the difference between O(n) and O(n log n) is most pronounced at very large n.
Question 7: Which data structure allows O(1) average-case insertion, deletion, and lookup?
- Binary search tree
- Sorted array
- Hash table (Correct answer)
- Min-heap
Correct answer: Hash table
A hash table achieves O(1) average-case operations through direct hashing, though worst-case can be O(n) due to collisions.
Algorithms Space & Time Complexity Analysis 2
What is the amortized time complexity of a single push operation on a dynamic array that doubles in size when full?