B2.4 Programming algorithms: notes and practice

What you need to know

Our summary of the topic in our own words, not the IB guide. Points marked HL are for Higher Level only.

• Explain what algorithmic efficiency means and why it is measured against input size rather than clock time
• State the meaning of the common complexity classes including constant, linear, logarithmic and quadratic time
• Determine the Big O complexity of a short piece of code from its loop structure
• Distinguish best, average and worst case for an algorithm
• Compare two algorithms for the same task on time and space and recommend one
• Write a linear search and state its complexity
• Write a binary search and explain why it requires sorted data
• Trace a binary search on a given sorted list and count the comparisons
• Write a bubble sort and state its complexity
• Write a selection sort and state its complexity
• Trace a sort pass by pass and give the list contents after each pass
• Compare bubble and selection sort on time and space complexity and on number of swaps
• Explain what recursion is and identify the base case and the recursive caseHL
• Compare a recursive and an iterative solution to the same problem on clarity and costHL
• Write a recursive algorithm for a standard problem such as factorial or FibonacciHL
• Trace a recursive call stack and state the return valueHL

Learn it

• Efficiency is measured against input size

  Lesson with 2 exercises

• Common complexity classes

  Lesson with 2 exercises

• Big O from loop structure

  Lesson with 3 exercises

Practice questions

Original questions written for the 2027 course, marked as you go. Easiest first.

• Name the growthWritten · Warm-up
• Timing on two computersWritten · Warm-up
• Count the comparisonsWritten · Core
• Handshake countWritten · Core
• Loops in a rowWritten · Core
• Tournament roundsWritten · Core
• Word finder growthWritten · Core
• Reading a recursive function that adds scoresWritten · Stretch
• Find a bookCoding · Stretch
• Binary search or linear search for book IDsWritten · Stretch
• Trace table: binary search for a book IDTrace table · Stretch
• Best score, recursivelyCoding · Stretch
• Recursion or loop for a top scoreWritten · Stretch
• Rank the scoresCoding · Stretch

Exam tips for B2.4

• Binary search only works on sorted data. Say so whenever you use it.
• Show the list after each pass when tracing a sort.
• Work out Big O from the loops: one loop over n is linear, a loop inside a loop is usually quadratic.