Algorithms & complexity worksheet with answers

Which sorting algorithm chooses a pivot and partitions the array into smaller and larger elements?

1. AMerge sort
2. BInsertion sort
3. CBubble sort
4. DQuicksort

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

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

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

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

How much stack space does a simple recursive factorial function fact(n) = n × fact(n − 1) use?

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

How does Prim's algorithm build a minimum spanning tree?

1. AIt runs breadth-first search and keeps the BFS tree
2. BIt removes the most expensive edge until no cycles remain
3. CIt grows one tree from a start vertex, adding the cheapest edge that leaves the tree
4. DIt sorts all edges by weight and adds each one unless it would form a cycle in the forest

A recurrence T(n) = 2T(n/2) + O(n) solves to:

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

Taking both endpoints of every edge in a maximal matching gives a vertex cover. How good is this cover?

1. AOf unknown quality compared to the optimum
2. BAlways a minimum vertex cover
3. CAt most log n times the minimum
4. DAt most twice the size of a minimum vertex cover

The 0/1 knapsack problem solved with dynamic programming takes O(nW) time. Why is this called pseudo-polynomial?

1. ABecause n is always small
2. BW is a number, so the time is exponential in the number of bits used to write W
3. CBecause the algorithm is randomised and its running time varies with each input
4. DBecause it only works for W = 0