Algorithms & complexity worksheet with answers

What does the worst-case running time of an algorithm describe?

1. AThe time it takes on the smallest input
2. BThe expected time it takes on a random input of size n
3. CThe maximum time it takes over all inputs of size n
4. DThe time it takes on a slow computer

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

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

Which notation describes an upper bound on growth?

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

Which sorting algorithm is stable?

1. AQuicksort (typical in-place version)
2. BHeap sort
3. CMerge sort
4. DSelection sort (typical version)

What does it mean that a problem has optimal substructure?

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

What is the time complexity of the Bellman–Ford algorithm on a graph with V vertices and E edges?

1. AO(E log V)
2. BO(V + E)
3. CO(V × E)
4. DO(V³ × E)

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

Karatsuba multiplication satisfies T(n) = 3T(n/2) + O(n). What does this solve to?

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