Algorithms & complexity worksheet with answers

What is the time complexity of linear search in an unsorted array of n elements (worst case)?

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

What is the best-case time complexity of insertion sort, on an already sorted array?

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

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

1. AMerge sort
2. BHeap sort
3. CBubble sort
4. DQuicksort

Why does dynamic programming give no real speed-up for merge sort?

1. ADynamic programming only works on graph problems, not on arrays
2. BIts subproblems do not overlap, so there is nothing to reuse
3. CMerge sort has no recursive structure
4. DMerge sort is already O(n)

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

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

What is the time complexity of the standard dynamic programming algorithm for the longest common subsequence of strings of lengths m and n?

1. AO(2^m+n)
2. BO(mn)
3. CO(mn log n)
4. DO(m + n)

Strassen's algorithm multiplies matrices using 7 instead of 8 recursive multiplications of half-size blocks. What is its running time?

1. AΘ(n^{log₂ 7}), about n^2.81
2. BΘ(n²)
3. CΘ(n³)
4. DΘ(n² log n)

Which two things must be shown to prove that a decision problem X is NP-complete?

1. AX is in NP, and a known NP-complete problem reduces to X in polynomial time
2. BX is in P, and X reduces to SAT
3. CX reduces to a problem in P, and X is in NP
4. DX has no polynomial algorithm, and X is decidable