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 worst-case time complexity of insertion sort?

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

What is recursion?

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

Which design strategy does merge sort use?

  1. ADivide and conquer
  2. BDynamic programming
  3. CBrute force
  4. DGreedy choice
4.Medium

A greedy algorithm:

  1. ATries every possible solution
  2. BAlways gives the optimal solution
  3. CUses only recursion
  4. DMakes the locally best choice at each step
5.Medium

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

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

What is the amortised time complexity of appending to a dynamic array that doubles its capacity when full?

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

Is 22n in O(2ⁿ)?

  1. ANo, because 22n = 4ⁿ and 4ⁿ / 2ⁿ = 2ⁿ grows without bound
  2. BNo, because 22n grows more slowly than 2ⁿ
  3. CYes, because both are exponential
  4. DYes, because constant factors in the exponent are always ignored in Big O
8.Hard

The halting problem shows that:

  1. ANo algorithm can decide for every program and input whether it halts
  2. BSome programs run faster on faster computers, so halting depends on hardware
  3. CEvery program eventually halts
  4. DLoops should be avoided

Answer key

  1. 1. D · O(n²)
  2. 2. A · A function that calls itself on smaller inputs
  3. 3. A · Divide and conquer
  4. 4. D · Makes the locally best choice at each step
  5. 5. B · O(n²)
  6. 6. C · O(1)
  7. 7. A · No, because 22n = 4ⁿ and 4ⁿ / 2ⁿ = 2ⁿ grows without bound
  8. 8. A · No algorithm can decide for every program and input whether it halts

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