Algorithms & complexity worksheet with answers

A problem is usually called tractable if:

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

What is log₂ 1024?

1. A512
2. B32
3. C12
4. D10

Which complexity class grows fastest for large n?

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

Why is the base of a logarithm usually left out in Big O, as in O(log n)?

1. ALogarithms are always rounded to integers
2. BThe base only matters for small n
3. CAll logarithms in computer science have base 10, so it is implied
4. DLogarithms with different bases differ only by a constant factor

What is the running time of LSD radix sort on n integers with d digits in base k?

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

Which algorithm finds the shortest paths from one source in a graph with non-negative edge weights?

1. AKruskal's algorithm
2. BDepth-first search
3. CDijkstra's algorithm
4. DBellman–Ford is required in all cases

What is the time complexity of building a binary heap from n unsorted elements with the bottom-up method?

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

A problem is NP-complete if it is:

1. AImpossible to solve
2. BSolvable in polynomial time
3. CIn NP and every NP problem reduces to it in polynomial time
4. DOutside NP but harder than all NP problems, such as the halting problem