Algorithms & complexity worksheet with answers

What is the base case of a recursive function?

1. AThe first line of the function
2. BA case that is answered directly without making another recursive call
3. CThe call that uses the most memory
4. DThe case with the largest input, which is handled before any recursive calls

What is the worst-case time complexity of merge sort?

1. AO(n²)
2. BO(n log n)
3. CO(n)
4. DO(log n)

What is the Big O of 3n² + 5n + 2?

1. AO(3n²)
2. BO(n³)
3. CO(5n)
4. DO(n²)

What is the time complexity of computing the n-th Fibonacci number with a bottom-up table?

1. AO(log n)
2. BO(2ⁿ)
3. CO(n²)
4. DO(n)

In a sorted array, you look for two elements that sum to a target by moving one pointer from each end inwards. What is the time complexity?

1. AO(log n)
2. BO(n²)
3. CO(n log n)
4. DO(n)

Why does dynamic programming give no real speed-up for merge sort?

1. AIts subproblems do not overlap, so there is nothing to reuse
2. BDynamic programming only works on graph problems, not on arrays
3. CMerge sort is already O(n)
4. DMerge sort has no recursive structure

What did the Cook–Levin theorem establish?

1. AEvery NP problem can be solved in exponential time
2. BP is not equal to NP
3. CThe Boolean satisfiability problem (SAT) is NP-complete
4. DThe halting problem is undecidable

Why does binary search not give O(log n) time on a singly linked list?

1. AReaching the middle element takes O(n) steps, since there is no direct index access
2. BComparisons on linked list nodes are slower
3. CLinked lists cannot be sorted
4. DBinary search needs at least twice the memory