AMCAT Algorithm Complexity 2 — Questions and Answers
Question 1: What is the time complexity of a loop: for(int i=1; i<=n; i*=2)?
- O(n)
- O(log n) (Correct answer)
- O(n log n)
- O(sqrt n)
Correct answer: O(log n)
The loop variable doubles each iteration: 1, 2, 4, 8, ... running O(log n) iterations.
i takes values 1, 2, 4, ..., 2^k where 2^k <= n. So k = floor(log2 n). The loop runs O(log n) times.
Question 2: Which sorting algorithm has O(n log n) time complexity in all cases (best, average, worst)?
- QuickSort
- Bubble Sort
- Merge Sort (Correct answer)
- Insertion Sort
Correct answer: Merge Sort
Merge Sort always divides into halves and merges, giving O(n log n) in all cases. QuickSort worst case is O(n^2).
Merge Sort splits into two halves and merges in O(n) — T(n) = 2T(n/2) + n = O(n log n) regardless of input order. QuickSort averages O(n log n) but worst case is O(n^2).
Question 3: The recurrence relation T(n) = T(n-1) + O(1) gives what time complexity?
- O(log n)
- O(n) (Correct answer)
- O(n squared)
- O(1)
Correct answer: O(n)
T(n) = T(n-1) + 1 expands to n steps: T(n) = n × O(1) = O(n).
T(n) = T(n−1) + 1 = T(n−2) + 2 = ... = T(0) + n = O(n). Linear time.
Question 4: What is the space complexity of an iterative binary search?
- O(n)
- O(log n)
- O(1) (Correct answer)
- O(n log n)
Correct answer: O(1)
Iterative binary search uses only a few variables (low, high, mid) regardless of input size — O(1) space.
Iterative binary search uses variables low, high, mid — no recursion stack. Memory usage is constant O(1). Recursive binary search uses O(log n) stack space.
Question 5: If an algorithm takes 2 seconds for n=100 and exhibits O(n squared) complexity, how long for n=1000?
- 20 seconds
- 200 seconds (Correct answer)
- 2000 seconds
- 20000 seconds
Correct answer: 200 seconds
O(n^2): n increases 10x so time increases 100x. 2 × 100 = 200 seconds.
Time is proportional to n^2. For n=100: T=2s. For n=1000 (10x larger): T = 2 × (1000/100)^2 = 2 × 100 = 200 seconds.
Question 6: Which notation gives the tight bound (both upper and lower bound) of an algorithm?
- Big-O (O)
- Big-Omega (Omega)
- Big-Theta (Theta) (Correct answer)
- Little-o (o)
Correct answer: Big-Theta (Theta)
Big-Theta describes the exact asymptotic behavior — the algorithm runs in both Omega(f(n)) and O(f(n)).
Theta(f(n)) means the algorithm takes at least c1·f(n) and at most c2·f(n) for large n. It is the intersection of O and Omega — the tightest possible characterization.
AMCAT Algorithm Complexity 2
What is the time complexity of a loop: for(int i=1; i<=n; i*=2)?