Algorithms & complexity worksheet with answers

What is the base case of a recursive function?

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

Accessing an element by index in an array takes:

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

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

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

Why do many library sorting routines switch to insertion sort for very small subarrays?

1. AInsertion sort is O(n log n) in the worst case
2. BInsertion sort has little overhead and is fast on small or nearly sorted inputs
3. CInsertion sort uses less memory than any other sorting algorithm on large inputs
4. DRecursive algorithms cannot handle arrays below 10 elements

Dynamic programming is useful when a problem has:

1. AA single loop
2. BOverlapping subproblems and optimal substructure
3. COnly random inputs
4. DNo subproblems at all, so it can be solved in one step

With coins of 1, 3 and 4 and an amount of 6, how many coins does the greedy "largest coin first" method use, compared to the optimum?

1. AGreedy uses 3 coins; the optimum is 3
2. BGreedy uses 4 coins; the optimum is 3
3. CGreedy uses 2 coins; the optimum is 2
4. DGreedy uses 3 coins; the optimum is 2

The halting problem shows that:

1. AEvery program eventually halts
2. BSome programs run faster on faster computers, so halting depends on hardware
3. CNo algorithm can decide for every program and input whether it halts
4. DLoops should be avoided

What is the running time of Dijkstra's algorithm with a binary heap on a graph with V vertices and E edges?

1. AO(V³)
2. BO((V + E) log V)
3. CO(V × E)
4. DO(V + E)