Algorithms & complexity worksheet with answers

An O(n) algorithm takes 3 seconds for n = 1 million. About how long does it take for n = 2 million?

1. A12 seconds
2. B9 seconds
3. C6 seconds
4. D3 seconds

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

1. ALogarithmic
2. BConstant
3. CQuadratic
4. DLinear

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

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

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

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

Dynamic programming is useful when a problem has:

1. AOverlapping subproblems and optimal substructure
2. BNo subproblems at all, so it can be solved in one step
3. COnly random inputs
4. DA single loop

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. BLogarithms are always rounded to integers
3. CThe base only matters for small n
4. DLogarithms with different bases differ only by a constant factor

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

1. AUsing recursion only on the left side
2. BSorting the input before running quicksort
3. CChoosing the pivot uniformly at random
4. DAlways choosing the first element

Which of these satisfiability problems is known to be solvable in polynomial time?

1. A2-SAT, where each clause has at most two literals
2. B3-SAT, where each clause has exactly three literals
3. CCircuit satisfiability
4. DGeneral SAT on formulas in conjunctive normal form