Algorithms & complexity worksheet with answers

What is a brute-force algorithm?

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

What are the three steps of a divide-and-conquer algorithm?

1. ARead, compute, write
2. BDivide, conquer, combine
3. CSort, search, return
4. DGuess, check, repeat

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 inserts each element into a growing sorted part by shifting
4. DIt repeatedly finds the minimum of the unsorted part and swaps it to the front

What is the time complexity of: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Why is the base of a logarithm usually left out in Big O, as in O(log n)?

1. AAll logarithms in computer science have base 10, so it is implied
2. BThe base only matters for small n
3. CLogarithms with different bases differ only by a constant factor
4. DLogarithms are always rounded to integers

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

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

The halting problem shows that:

1. AEvery program eventually halts
2. BNo algorithm can decide for every program and input whether it halts
3. CSome programs run faster on faster computers, so halting depends on hardware
4. DLoops should be avoided

Is 2²ⁿ in O(2ⁿ)?

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