Algorithms & complexity worksheet with answers

What is the time complexity of finding the largest value in an unsorted array of n numbers?

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

Which sorting algorithm repeatedly swaps adjacent elements that are in the wrong order?

1. ABubble sort
2. BHeap sort
3. CMerge sort
4. DQuicksort

What is log₂ 1024?

1. A32
2. B12
3. C10
4. D512

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

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

What does it mean that a problem has optimal substructure?

1. AEvery subproblem has the same size
2. BThe problem has exactly one optimal solution, which every subproblem shares
3. CAn optimal solution can be built from optimal solutions of its subproblems
4. DThe problem can be solved in constant time

How much stack space does a simple recursive factorial function fact(n) = n × fact(n − 1) use?

1. AO(1)
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. AKruskal's algorithm
2. BFloyd–Warshall
3. CDijkstra's algorithm
4. DPrim's algorithm starting from one node

Is 2²ⁿ in O(2ⁿ)?

1. AYes, because both are exponential
2. BNo, because 2²ⁿ grows more slowly than 2ⁿ
3. CYes, because constant factors in the exponent are always ignored in Big O
4. DNo, because 2²ⁿ = 4ⁿ and 4ⁿ / 2ⁿ = 2ⁿ grows without bound