Algorithms & complexity worksheet with answers

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

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

A problem is usually called tractable if:

1. AIt has no solution
2. BIt can be solved in constant time
3. CIt can only be solved by trying every possibility
4. DIt can be solved in polynomial time

Space complexity measures:

1. AThe number of lines of code
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 physical size of the computer

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

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

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

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

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

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

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

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

Which two things must be shown to prove that a decision problem X is NP-complete?

1. AX reduces to a problem in P, and X is in NP
2. BX has no polynomial algorithm, and X is decidable
3. CX is in NP, and a known NP-complete problem reduces to X in polynomial time
4. DX is in P, and X reduces to SAT