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 linear search in an unsorted array of n elements (worst case)?

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

What is log₂ 1024?

  1. A32
  2. B10
  3. C12
  4. D512
3.Easy

What is O(2ⁿ) growth called?

  1. ALogarithmic
  2. BPolynomial
  3. CExponential
  4. DLinear
4.Medium

What is the running time of LSD radix sort on n integers with d digits in base k?

  1. AO(d(n + k))
  2. BO(n²)
  3. CO(n log n)
  4. DO(dn log k)
5.Medium

In a sorted array, you look for two elements that sum to a target by moving one pointer from each end inwards. What is the time complexity?

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

Dynamic programming is useful when a problem has:

  1. AOverlapping subproblems and optimal substructure
  2. BOnly random inputs
  3. CA single loop
  4. DNo subproblems at all, so it can be solved in one step
7.Hard

Why does any comparison-based search in a sorted array need Ω(log n) comparisons in the worst case?

  1. AA decision tree with n possible outcomes must have depth at least log₂ n
  2. BBinary search is the only possible algorithm, and it needs log₂ n comparisons
  3. CEvery element must be compared at least once
  4. DComparisons take logarithmic time each
8.Hard

What is the difference between an undecidable problem and an intractable one?

  1. AAn undecidable problem has no algorithm for all inputs; an intractable one has one, but it is too slow
  2. BIntractable problems cannot be solved by any algorithm, while undecidable ones only need exponential time
  3. CUndecidable problems are in NP, while intractable problems are in P
  4. DBoth mean the problem has no algorithm at all

Answer key

  1. 1. C · O(n)
  2. 2. B · 10
  3. 3. C · Exponential
  4. 4. A · O(d(n + k))
  5. 5. C · O(n)
  6. 6. A · Overlapping subproblems and optimal substructure
  7. 7. A · A decision tree with n possible outcomes must have depth at least log₂ n
  8. 8. A · An undecidable problem has no algorithm for all inputs; an intractable one has one, but it is too slow

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