Algorithms & complexity worksheet with answers

What does f(n) = Θ(g(n)) mean?

1. Af grows strictly faster than g
2. Bf grows strictly slower than g
3. Cf is always smaller than g for every n, so g bounds it from above but never from below
4. Df grows at the same rate as g, bounded above and below by constant multiples of g

How does selection sort work?

1. AIt splits the array in halves and merges them
2. BIt repeatedly swaps neighbouring elements that are in the wrong order
3. CIt repeatedly finds the minimum of the unsorted part and swaps it to the front
4. DIt inserts each element into a growing sorted part by shifting

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

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

What does amortised analysis measure?

1. AThe expected cost over random inputs
2. BThe cost of an algorithm on the best input
3. CThe average cost per operation over a worst-case sequence of operations
4. DThe cost of the single most expensive operation anywhere in the sequence

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

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

A greedy algorithm:

1. AAlways gives the optimal solution
2. BUses only recursion
3. CTries every possible solution
4. DMakes the locally best choice at each step

Why does any comparison-based search in a sorted array need Ω(log n) comparisons in the worst case?

1. ABinary search is the only possible algorithm, and it needs log₂ n comparisons
2. BComparisons take logarithmic time each
3. CEvery element must be compared at least once
4. DA decision tree with n possible outcomes must have depth at least 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. BDijkstra's algorithm
3. CFloyd–Warshall
4. DPrim's algorithm starting from one node