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 finding the nth Fibonacci number using dynamic programming (memoization)?
Answer: O(n)
With memoization, each Fibonacci value is computed once. There are n unique subproblems — O(n) time.
What is the time complexity of Dijkstra's shortest-path algorithm using a binary heap priority queue?
Answer: O(E log V)
With a binary heap, each edge relaxation is O(log V) and there are E relaxations — O(E log V).
Which of the following has the best average-case time complexity for sorting?
Answer: Merge Sort — O(n log n)
Merge Sort guarantees O(n log n) average and worst case, which is optimal for comparison-based sorting.
An algorithm with O(n!) complexity is described as:
Answer: Factorial/Super-exponential
O(n!) is factorial time complexity, which grows faster than exponential O(2^n). It appears in brute-force permutation problems.
What is the time complexity of: for(int i=0; i<n; i++) for(int j=i; j<n; j++) { }?
Answer: O(n squared)
Total iterations = n + (n-1) + ... + 1 = n(n+1)/2 = O(n^2).
What is the average time complexity of searching in a hash table?
Answer: O(1)
On average, a hash table lookup computes the hash and accesses the bucket in constant time — O(1).