Algorithms & complexity worksheet with answers

Which complexity class grows fastest for large n?

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

What is the worst-case time complexity of insertion sort?

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

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

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

With coins of 1, 3 and 4 and an amount of 6, how many coins does the greedy "largest coin first" method use, compared to the optimum?

1. AGreedy uses 4 coins; the optimum is 3
2. BGreedy uses 2 coins; the optimum is 2
3. CGreedy uses 3 coins; the optimum is 3
4. DGreedy uses 3 coins; the optimum is 2

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

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

Why does dynamic programming give no real speed-up for merge sort?

1. ADynamic programming only works on graph problems, not on arrays
2. BMerge sort has no recursive structure
3. CIts subproblems do not overlap, so there is nothing to reuse
4. DMerge sort is already O(n)

What is the running time of Dijkstra's algorithm with a binary heap on a graph with V vertices and E edges?

1. AO(V³)
2. BO(V + E)
3. CO((V + E) log V)
4. DO(V × E)

Which algorithm finds a minimum spanning tree by repeatedly adding the cheapest edge that does not form a cycle?

1. AKruskal's algorithm
2. BPrim's algorithm starting from one node
3. CFloyd–Warshall
4. DDijkstra's algorithm