Algorithms & complexity worksheet with answers

Which notation describes an upper bound on growth?

1. ABig Theta
2. BBig Omega
3. CBig O
4. DLittle omega

What is O(2ⁿ) growth called?

1. AExponential
2. BLinear
3. CLogarithmic
4. DPolynomial

What is the running time of counting sort for n integers in the range 0 to k?

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

What does the recurrence T(n) = 2T(n/2) + O(1) solve to?

1. AO(log n)
2. BO(n)
3. CO(n log n)
4. DO(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 runs breadth-first search and keeps the BFS tree
3. CIt removes the most expensive edge until no cycles remain
4. DIt grows one tree from a start vertex, adding the cheapest edge that leaves the tree

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

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

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

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

What is the time complexity of: for i = 1 to n: for (j = i; j ≤ n; j = j + i) do O(1) work?

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