Algorithms & complexity worksheet with answers

Which design strategy does merge sort use?

1. ABrute force
2. BDivide and conquer
3. CDynamic programming
4. DGreedy choice

Which notation describes an upper bound on growth?

1. ABig O
2. BBig Omega
3. CBig Theta
4. DLittle omega

Which sorting algorithm repeatedly swaps adjacent elements that are in the wrong order?

1. AHeap sort
2. BBubble sort
3. CQuicksort
4. DMerge sort

About how many comparisons does binary search need in the worst case on a sorted array of 1,000,000 elements?

1. AAbout 500,000
2. BAbout 20
3. CAbout 1,000
4. DAbout 100

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

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

What does it mean that a problem has optimal substructure?

1. AAn optimal solution can be built from optimal solutions of its subproblems
2. BEvery subproblem has the same size
3. CThe problem can be solved in constant time
4. DThe problem has exactly one optimal solution, which every subproblem shares

Which statement about little-o notation is correct?

1. An² = o(n)
2. Bn = o(n²), but n is not o(n)
3. C2n = o(n), because 2n grows slowly
4. Dn = o(n), since every function is little-o of itself

Is 2²ⁿ in O(2ⁿ)?

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