Algorithms & complexity worksheet with answers

What is the worst-case time complexity of insertion sort?

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

What is recursion?

1. AA loop that never ends
2. BA sorting method
3. CA function that calls itself on smaller inputs
4. DA type of data structure

What is the base case of a recursive function?

1. AThe call that uses the most memory
2. BThe first line of the function
3. CThe case with the largest input, which is handled before any recursive calls
4. DA case that is answered directly without making another recursive call

Why do many library sorting routines switch to insertion sort for very small subarrays?

1. AInsertion sort uses less memory than any other sorting algorithm on large inputs
2. BInsertion sort has little overhead and is fast on small or nearly sorted inputs
3. CInsertion sort is O(n log n) in the worst case
4. DRecursive algorithms cannot handle arrays below 10 elements

What is the time complexity of: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

What does it mean that a problem has optimal substructure?

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

The Held–Karp dynamic programming algorithm solves the travelling salesman problem exactly. What is its running time for n cities?

1. AO(n² 2ⁿ)
2. BO(2^n²)
3. CO(n³)
4. DO(n!)

Which definition of the class NP is correct?

1. AProblems that are not polynomial
2. BDecision problems whose yes-answers can be verified in polynomial time given a certificate
3. CProblems that cannot be solved in polynomial time
4. DProblems that no algorithm can solve