Algorithms & complexity worksheet with answers

What is a brute-force algorithm?

1. AOne that tries all possible candidate solutions
2. BOne that runs on many processors
3. COne that always uses recursion
4. DOne that guesses an answer at random

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

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

An algorithm's running time is O(n). What is this growth called?

1. ALogarithmic
2. BLinear
3. CQuadratic
4. DConstant

What does the recurrence T(n) = T(n/2) + O(1) solve to?

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

A greedy algorithm:

1. AMakes the locally best choice at each step
2. BUses only recursion
3. CAlways gives the optimal solution
4. DTries every possible solution

What does amortised analysis measure?

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

What is the time complexity of: for i = 1 to n: for (j = i; j ≤ n; j = j + i) do O(1) work?

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

A problem is NP-complete if it is:

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