Algorithms & complexity worksheet with answers

How does selection sort work?

1. AIt splits the array in halves and merges them
2. BIt repeatedly finds the minimum of the unsorted part and swaps it to the front
3. CIt inserts each element into a growing sorted part by shifting
4. DIt repeatedly swaps neighbouring elements that are in the wrong order

Space complexity measures:

1. AThe physical size of the computer
2. BThe amount of memory an algorithm needs as input grows
3. CThe disk space of the program file once it is compiled
4. DThe number of lines of code

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

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

Is it correct to say that an O(n²) algorithm is also O(n³)?

1. ANo, because n³ is smaller than n² for large n
2. BNo, because Big O must always state the exact growth rate of the function
3. CYes, because Big O is an upper bound and n² grows no faster than n³
4. DYes, but only if n is smaller than 100

A function runs one loop of n iterations and then, separately, another loop of n iterations. What is its time complexity?

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

Breadth-first search on an unweighted graph finds:

1. AA topological order in all graphs
2. BShortest paths in graphs that contain negative edge weights
3. CShortest paths in number of edges from the start node
4. DThe minimum spanning tree

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

1. ABecause it only works for W = 0
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 n is always small

Strassen's algorithm multiplies matrices using 7 instead of 8 recursive multiplications of half-size blocks. What is its running time?

1. AΘ(n² log n)
2. BΘ(n³)
3. CΘ(n^{log₂ 7}), about n^2.81
4. DΘ(n²)