Algorithms & complexity worksheet with answers

What does it mean if an operation runs in O(1) time?

1. AIt always takes exactly one second
2. BIts running time does not grow with the input size
3. CIt can only be run once
4. DIt processes exactly one element per second of running time

What is the best-case time complexity of insertion sort, on an already sorted array?

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

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

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

Dynamic programming is useful when a problem has:

1. ANo subproblems at all, so it can be solved in one step
2. BOverlapping subproblems and optimal substructure
3. COnly random inputs
4. DA single loop

In a sorted array, you look for two elements that sum to a target by moving one pointer from each end inwards. What is the time complexity?

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

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

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

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

1. AFloyd–Warshall
2. BKruskal's algorithm
3. CDijkstra's algorithm
4. DPrim's algorithm starting from one node

Which bound is correct for log(n!)?

1. AΘ(log n)
2. BΘ(n²)
3. CΘ(n log n)
4. DΘ(n)