Algorithms & complexity worksheet with answers

An O(n²) algorithm takes 1 second for n = 1000. About how long does it take for n = 2000?

1. A8 seconds
2. B2 seconds
3. C4 seconds
4. D1 second

What is the Big O of 3n² + 5n + 2?

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

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

1. ALinear
2. BQuadratic
3. CLogarithmic
4. DConstant

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

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

Which statement about a recursive function without a reachable base case is correct?

1. AThe compiler always turns it into a loop that ends safely
2. BIt keeps calling itself until the call stack overflows
3. CIt runs in O(1) time
4. DIt returns 0 automatically

Quicksort always uses the first element as pivot. On which input does it show its worst-case behaviour?

1. AAn array in random order
2. BAn array of length 2
3. CAn array that is already sorted
4. DAn array whose elements are all different

Which technique gives an expected O(n log n) running time for quicksort on any input?

1. ASorting the input before running quicksort
2. BAlways choosing the first element
3. CChoosing the pivot uniformly at random
4. DUsing recursion only on the left side

Topological sorting is possible only for:

1. ADirected acyclic graphs
2. BGraphs with negative weights
3. CComplete graphs
4. DUndirected graphs