Algorithms & complexity worksheet with answers

Free printable Algorithms & complexity worksheet: 8 problems from easy to exam level, with an answer key. Print it or save it as a PDF.

New worksheetPractise online with hints

For teachers: free to print, copy and use in class. Every new worksheet has new values and its own answer key. A link to ExamProblems on your course page is appreciated.

Name: ____________________   Date: ____________

1.Easy

What is the time complexity of finding the largest value in an unsorted array of n numbers?

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

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

  1. ASort, search, return
  2. BGuess, check, repeat
  3. CDivide, conquer, combine
  4. DRead, compute, write
3.Easy

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

  1. AMerge sort
  2. BBubble sort
  3. CHeap sort
  4. DQuicksort
4.Medium

Which sorting algorithm is stable?

  1. ASelection sort (typical version)
  2. BMerge sort
  3. CHeap sort
  4. DQuicksort (typical in-place version)
5.Medium

What does the Floyd–Warshall algorithm compute, and how fast?

  1. AShortest paths from one source vertex to all others in O(V + E)
  2. BA minimum spanning tree in O(E log V)
  3. CA topological order in O(V²)
  4. DShortest paths between all pairs of vertices in O(V³)
6.Medium

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

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

To show that a new problem X is NP-hard, what must you do?

  1. AReduce X to a known NP-hard problem in polynomial time
  2. BReduce a known NP-hard problem to X in polynomial time
  3. CShow that X has no polynomial algorithm for small inputs
  4. DShow that X can be verified in polynomial time
8.Hard

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

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

Answer key

  1. 1. A · O(n)
  2. 2. C · Divide, conquer, combine
  3. 3. B · Bubble sort
  4. 4. B · Merge sort
  5. 5. D · Shortest paths between all pairs of vertices in O(V³)
  6. 6. D · O(2ⁿ)
  7. 7. B · Reduce a known NP-hard problem to X in polynomial time
  8. 8. D · O(n log n)

Full step-by-step solutions: practise this topic on examproblems.com.