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 O(2ⁿ) growth called?

  1. APolynomial
  2. BLinear
  3. CLogarithmic
  4. DExponential
2.Easy

An algorithm with two nested loops, each running n times, typically has which complexity?

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

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

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

The time complexity of naive recursive Fibonacci (fib(n) = fib(n−1) + fib(n−2)) is:

  1. AExponential
  2. BLinear
  3. CLogarithmic
  4. DConstant
5.Medium

What is the time complexity of multiplying two n × n matrices with the standard triple loop?

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

How much stack space does a simple recursive factorial function fact(n) = n × fact(n − 1) use?

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

How do n! and 2ⁿ compare for large n?

  1. A2ⁿ grows faster than n!
  2. BThey grow at the same rate
  3. Cn! is O(n²)
  4. Dn! grows faster than 2ⁿ
8.Hard

A problem is NP-complete if it is:

  1. ASolvable in polynomial time
  2. BIn NP and every NP problem reduces to it in polynomial time
  3. COutside NP but harder than all NP problems, such as the halting problem
  4. DImpossible to solve

Answer key

  1. 1. D · Exponential
  2. 2. A · O(n²)
  3. 3. B · O(n)
  4. 4. A · Exponential
  5. 5. C · O(n³)
  6. 6. D · O(n)
  7. 7. D · n! grows faster than 2ⁿ
  8. 8. B · In NP and every NP problem reduces to it in polynomial time

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