Algorithms & complexity worksheet with answers

What is the time complexity of finding the largest value in an unsorted array of n numbers?

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

What is O(2ⁿ) growth called?

1. AExponential
2. BPolynomial
3. CLinear
4. DLogarithmic

What is the time complexity of binary search on a sorted array?

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

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

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

Quicksort always uses the first element as pivot. On which input does it show its worst-case behaviour?

1. AAn array in random order
2. BAn array that is already sorted
3. CAn array whose elements are all different
4. DAn array of length 2

Which statement about a recursive function without a reachable base case is correct?

1. AIt keeps calling itself until the call stack overflows
2. BIt runs in O(1) time
3. CThe compiler always turns it into a loop that ends safely
4. DIt returns 0 automatically

What are the time and space costs of computing the n-th Fibonacci number with a loop that keeps only the last two values?

1. AO(n) time and O(n) space
2. BO(log n) time and O(n) space
3. CO(2ⁿ) time and O(1) space
4. DO(n) time and O(1) space

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

1. AAlways a minimum vertex cover
2. BAt most log n times the minimum
3. COf unknown quality compared to the optimum
4. DAt most twice the size of a minimum vertex cover