Algorithms & complexity worksheet with answers

What is the base case of a recursive function?

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

An algorithm with two nested loops, each running n times, typically has which complexity?

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

What does it mean if an operation runs in O(1) time?

1. AIt always takes exactly one second
2. BIt can only be run once
3. CIts running time does not grow with the input size
4. DIt processes exactly one element per second of running time

What is the worst-case time complexity of quicksort?

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

You sort an array of n elements once and then answer k membership queries with binary search. What is the total cost?

1. AO(n + k)
2. BO(k n log n)
3. CO(n log n + k log n)
4. DO(nk)

A greedy algorithm:

1. AUses only recursion
2. BAlways gives the optimal solution
3. CMakes the locally best choice at each step
4. DTries every possible solution

The halting problem shows that:

1. ANo algorithm can decide for every program and input whether it halts
2. BLoops should be avoided
3. CEvery program eventually halts
4. DSome programs run faster on faster computers, so halting depends on hardware

Why is the average lookup in a hash table O(1) but the worst case O(n)?

1. AMany keys may collide into the same bucket
2. BHash functions are slow
3. CArrays have O(n) access
4. DKeys must be sorted first