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 log₂ 1024?

  1. A10
  2. B32
  3. C512
  4. D12
2.Easy

How does selection sort work?

  1. AIt splits the array in halves and merges them
  2. BIt repeatedly finds the minimum of the unsorted part and swaps it to the front
  3. CIt repeatedly swaps neighbouring elements that are in the wrong order
  4. DIt inserts each element into a growing sorted part by shifting
3.Easy

What is the time complexity of linear search in an unsorted array of n elements (worst case)?

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

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

  1. AO(n²)
  2. BO(n)
  3. CO(n² log n)
  4. DO(n³)
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³)
  2. BO(n log n)
  3. CO(n)
  4. DO(n²)
6.Medium

What is the time complexity of: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

The halting problem shows that:

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

What is the running time of Dijkstra's algorithm with a binary heap on a graph with V vertices and E edges?

  1. AO(V + E)
  2. BO(V × E)
  3. CO((V + E) log V)
  4. DO(V³)

Answer key

  1. 1. A · 10
  2. 2. B · It repeatedly finds the minimum of the unsorted part and swaps it to the front
  3. 3. D · O(n)
  4. 4. D · O(n³)
  5. 5. D · O(n²)
  6. 6. C · O(n log n)
  7. 7. C · No algorithm can decide for every program and input whether it halts
  8. 8. C · O((V + E) log V)

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