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

A loop starts with i = 1 and doubles i each iteration until i > n. How many iterations does it run?

  1. AAbout n²
  2. BAbout n
  3. CAbout log₂ n
  4. DAbout n / 2
2.Easy

Which notation describes a lower bound on growth?

  1. AO (Big O)
  2. Bo (little o)
  3. CΘ (Big Theta)
  4. DΩ (Big Omega)
3.Easy

Which of these grows slowest as n becomes large?

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

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

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

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

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

A recurrence T(n) = 2T(n/2) + O(n) solves to:

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

Shortest simple paths can be found in polynomial time. What is known about finding the longest simple path between two vertices in a general graph?

  1. AIt is always solvable in O(V + E)
  2. BIt can be solved by Dijkstra's algorithm with negated weights
  3. CIt is NP-hard
  4. DIt is undecidable
8.Hard

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

  1. AΘ(nlog₂ 7), about n2.81
  2. BΘ(n2)
  3. CΘ(n³)
  4. DΘ(n² log n)

Answer key

  1. 1. C · About log₂ n
  2. 2. D · Ω (Big Omega)
  3. 3. A · O(log n)
  4. 4. C · O(log n)
  5. 5. D · O(n)
  6. 6. C · O(n log n)
  7. 7. C · It is NP-hard
  8. 8. A · Θ(nlog₂ 7), about n2.81

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