Algorithm Complexity Flashcards
6 cards from real AMCAT practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.
Read the first 6 Algorithm Complexity flashcards as text
What is the time complexity of a loop: for(int i=1; i<=n; i*=2)?
Answer: O(log n)
The loop variable doubles each iteration: 1, 2, 4, 8, ... running O(log n) iterations.
Which sorting algorithm has O(n log n) time complexity in all cases (best, average, worst)?
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).
The recurrence relation T(n) = T(n-1) + O(1) gives what time complexity?
Answer: O(n)
T(n) = T(n-1) + 1 expands to n steps: T(n) = n × O(1) = O(n).
What is the space complexity of an iterative binary search?
Answer: O(1)
Iterative binary search uses only a few variables (low, high, mid) regardless of input size — O(1) space.
If an algorithm takes 2 seconds for n=100 and exhibits O(n squared) complexity, how long for n=1000?
Answer: 200 seconds
O(n^2): n increases 10x so time increases 100x. 2 × 100 = 200 seconds.
Which notation gives the tight bound (both upper and lower bound) of an algorithm?
Answer: Big-Theta (Theta)
Big-Theta describes the exact asymptotic behavior — the algorithm runs in both Omega(f(n)) and O(f(n)).