SHSubjectHub

Classification of algorithms: Big-O, tractability and the Halting problem

AQA 75174.4 L5A-levelLesson packSubscription
Also online

This worksheet marks itself

Set it as homework or classwork and every answer is marked as pupils go, with feedback on what they got wrong. The scores go straight into your mark book, so you can see who needs help before the next lesson.

  • 12 questions
  • 39 marks
  • about 40 minutes
  • marked instantly

Question types: short answer, multiple choice, true or false, matching.

Try it with a class, freeHow it works

Try one from this worksheet

An algorithm takes 2ⁿ + n³ + 7 steps for a problem of size n. Identify its time complexity.

Pick an answer: it's marked straight away, just as your pupils would see it.

About this resource

AQA A-level Computer Science (7517) 4.4.4.1-4.4.4.7 Classification of algorithms: comparing algorithms, maths for Big-O, order of complexity, limits of computation, tractable and intractable problems, computable and non-computable problems, the Halting problem. C# lesson 5 of 6 in 4.4 Theory of c…

21 slides.

Lesson outline

  1. Do Now: count the steps
  2. Do Now: answers
  3. Key idea: Comparing algorithms: functions of n
  4. Key idea: Big-O: how the steps grow
  5. Quick check: which grows fastest?
  6. Key idea: Deriving the complexity of an algorithm
  7. Key idea: Tractable and intractable problems
  8. Quick check: tractable or not?
  9. Key idea: Heuristics: the nearest neighbour
  10. Key idea: Computable? The Halting problem
  11. Set 1: factorials, permutations and powers
  12. Set 2: count the steps, find the order
Unit bundle4.4 Theory of computation · full lessons
Part of: 4.4 Theory of computation · full lessons: the whole unitEvery resource in the unit in one zip.

More from 4.4 Theory of computation · full lessons