For teachers: free to print, copy and use in class. Every new worksheet has new values and its own answer key. A link to ExamProblems on your course page is appreciated.
Name: ____________________ Date: ____________
1.Easy
What is the base case of a recursive function?
AThe case with the largest input, which is handled before any recursive calls
BThe first line of the function
CA case that is answered directly without making another recursive call
DThe call that uses the most memory
2.Easy
Which complexity class grows fastest for large n?
AO(n³)
BO(n²)
CO(2ⁿ)
DO(n log n)
3.Easy
What is the worst-case time complexity of merge sort?
AO(log n)
BO(n)
CO(n log n)
DO(n²)
4.Medium
The lower bound for comparison-based sorting in the worst case is:
AΩ(n²)
BΩ(log n)
CΩ(n log n)
DΩ(n)
5.Medium
What is the time complexity of the Bellman–Ford algorithm on a graph with V vertices and E edges?
AO(V × E)
BO(E log V)
CO(V³ × E)
DO(V + E)
6.Medium
What is the amortised time complexity of appending to a dynamic array that doubles its capacity when full?
AO(n)
BO(1)
CO(n²)
DO(log n)
7.Hard
Which algorithm finds a minimum spanning tree by repeatedly adding the cheapest edge that does not form a cycle?
AFloyd–Warshall
BKruskal's algorithm
CDijkstra's algorithm
DPrim's algorithm starting from one node
8.Hard
What are the time and space costs of computing the n-th Fibonacci number with a loop that keeps only the last two values?
AO(n) time and O(1) space
BO(2ⁿ) time and O(1) space
CO(log n) time and O(n) space
DO(n) time and O(n) space
Answer key
1. C · A case that is answered directly without making another recursive call
2. C · O(2ⁿ)
3. C · O(n log n)
4. C · Ω(n log n)
5. A · O(V × E)
6. B · O(1)
7. B · Kruskal's algorithm
8. A · O(n) time and O(1) space
Full step-by-step solutions: practise this topic on examproblems.com.