Scribe logoScribeNotes & practice
Sign inStart free
  1. Notes
  2. ›IB Computer Science
  3. ›B2 Programming
  4. ›B2.4 Programming algorithms

IB Computer Science · B2 · Programming

B2.4 Programming algorithms

Describe the steps of a linear search, explain how a bubble sort works, trace simple algorithms and compare the efficiency of two basic algorithms.

  • 5 min read
  • 6 parts
  • 10 questions
  • Draft
Start a Quick 5 on this topic→Jump to the 10 questions
1/6A linear search checks each item in turn
  1. 1A linear search checks each item in turn
  2. 2A trace table lets you follow an algorithm by hand
  3. 3Bubble sort swaps neighbouring items until the list is ordered
  4. 4Tracing a bubble sort shows how each pass works
  5. 5Efficiency describes how the work grows with list size
  6. 6Binary search needs fewer comparisons but requires sorted data
  7. Check your recall
  8. Practice: 10 questions
1

Part 1 of 6: A linear search checks each item in turn

Suppose you look for one name on an unsorted guest list. You start at the top and read each name until you find a match or reach the end. The name you want is the target, and this method is a linear search.

  • Set the position to the first item.
  • Compare the item at that position with the target.
  • If they match, report the position and stop.
  • Otherwise, move to the next position.
  • If the end is reached without a match, report that the target is absent.

The list does not need to be sorted. The method is simple and always correct, but it can be slow on long lists.

Key term

linear search

A linear search is an algorithm that examines list items one at a time in order, and works on sorted or unsorted data.

Part 1 done

2

Part 2 of 6: A trace table lets you follow an algorithm by hand

Before moving on to sorting, you need a way to check what an algorithm does. A trace table records the value of each variable after every step. Use one column per variable and one row per change. It lets you test an algorithm without running it.

Worked example

Trace a linear search

Trace a linear search for the target 9 in the list 7, 3, 9, 4. Positions start at 0.
  1. 1
    Position 0 holds 7. It is not 9, so move to the next position.
  2. 2
    Position 1 holds 3. It is not 9, so move on again.
  3. 3
    Position 2 holds 9. This matches the target, so the search stops.

Answer: The search returns position 2 after 3 comparisons.

Tracing also locates faults. If the output is wrong, find the first row where a value looks wrong. The fault lies at or just before that step.

Exam tip

Copy unchanged values down into each new row. Skipping rows hides the order of events, and that order earns marks.

Key term

trace table

A trace table is a table that records the value of every variable after each step of an algorithm.

Part 2 done

Quick check

One question on the part you just read

Easy

Identify the description that matches a linear search.
Show answer and explanation

Answer: A · Worked explanation

A linear search examines items one at a time from the start, so it works on sorted or unsorted lists. Halving a sorted list describes binary search, which is a different algorithm. Swapping neighbouring items describes bubble sort, and recording variable values describes a trace table, so neither matches a search.
3

Part 3 of 6: Bubble sort swaps neighbouring items until the list is ordered

Searching is easier on ordered data, so now consider how to sort a list. A bubble sort compares each pair of neighbouring items. If a pair is in the wrong order, the two items swap. Here the list is sorted in ascending order, smallest first.

One full run through the list is a pass. After the first pass, the largest item has moved to the end. Each later pass places the next largest item.

The algorithm stops when a whole pass makes no swaps. This final pass confirms that the list is in order.

Common mistake

A single pass does not sort the whole list. It only guarantees that one more item reaches its final place.

Key terms · tap one for its definition

bubble sort

A bubble sort is a sorting algorithm that repeatedly compares neighbouring items and swaps them when out of order, until no swaps are needed.

pass

A pass is one complete run through the list in a bubble sort, comparing each neighbouring pair once.

Part 3 done

4

Part 4 of 6: Tracing a bubble sort shows how each pass works

Now apply the trace method to a short list. To swap two items, a program needs a temporary variable. It stores the first value, copies the second value across, then places the stored value in the second position. Check each pass against one rule: compare neighbours, and swap if they are out of order.

Worked example

Trace a bubble sort

Sort 5, 3, 8, 1 into ascending order using a bubble sort. Show the list after each pass.
  1. 1
    Pass 1: swap 5 and 3, keep 5 and 8, then swap 8 and 1. The list is 3, 5, 1, 8.
  2. 2
    Pass 2: keep 3 and 5, swap 5 and 1, then keep 5 and 8. The list is 3, 1, 5, 8.
  3. 3
    Pass 3: swap 3 and 1, then keep the other pairs. The list is 1, 3, 5, 8.
  4. 4
    Pass 4: no pair is out of order, so no swaps happen and the algorithm stops.

Answer: The sorted list is 1, 3, 5, 8. Three passes make swaps and a fourth pass confirms the order.

Notice that the largest item reaches the end in the first pass. Later passes can ignore the items already in place. A program that stops after a pass with no swaps finishes early on lists that are nearly sorted.

Part 4 done

Quick check

One question on the part you just read

Easy

State what a bubble sort does when two neighbouring items are in the wrong order.
Show answer and explanation

Answer: C · Worked explanation

Swapping out-of-order neighbours is the basic move of a bubble sort. After the swap, the sort compares the next pair in the same pass. Discarding or overwriting an item would lose data, and ending the sort at the first wrong pair would leave the list unsorted.
5

Part 5 of 6: Efficiency describes how the work grows with list size

Both algorithms give correct results, so the next question is how much work each does. Efficiency describes how the work an algorithm needs grows as the input grows. A simple measure counts comparisons.

The worst case is the input that makes the algorithm do the most work. For a list of nnn items, a linear search needs up to nnn comparisons. This happens when the target is last or absent.

Bubble sort grows faster, roughly with n2n^2n2. Doubling the list size about quadruples the comparisons.

Exam tip

Describe efficiency as a change in work as nnn grows. A single timing on one computer is not a fair comparison.

Key terms · tap one for its definition

efficiency

The efficiency of an algorithm is a measure of the time or number of steps it needs, usually compared as input size grows.

worst case

The worst case is the input of a given size that makes an algorithm perform the greatest number of steps.

Part 5 done

6

Part 6 of 6: Binary search needs fewer comparisons but requires sorted data

Linear search is not the only way to find an item. A binary search compares the target with the middle item of a sorted list. It then discards the half that cannot hold the target and repeats on the other half.

Each step halves the remaining items. A sorted list of 1000 items needs at most about 10 comparisons, while a linear search could need 1000.

Figure 1. Binary search needs far fewer comparisons than linear search as the list grows.

Linear search compared with binary search

FeatureLinear searchBinary search
List must be sortedNoYes
Worst-case comparisonsnnnabout log⁡2n\log_2 nlog2​n
Best suited toShort or unsorted listsLong sorted lists
Feature
List must be sorted
Linear search
No
Binary search
Yes
Feature
Worst-case comparisons
Linear search
nnn
Binary search
about log⁡2n\log_2 nlog2​n
Feature
Best suited to
Linear search
Short or unsorted lists
Binary search
Long sorted lists

Common mistake

Binary search fails on an unsorted list. Sorting first costs extra work, so it pays off mainly when many searches follow.

Key term

binary search

A binary search is an algorithm that finds a target in a sorted list by repeatedly halving the part still to be searched.

Note read

Check your recall[14 marks]

6 written questions. Answer each one in your head or on paper, then open the mark scheme.

  1. 1.Describe[3 marks]

    Describe the steps of a linear search for a target in a list.

    Show mark schemeHide mark scheme

    Model answer

    Start at the first item and compare it with the target. If it matches, report its position and stop; otherwise move to the next item. If the end is reached without a match, report that the target is absent.

    • 1 mark for starting at the first item and comparing each item with the target in turn
    • 1 mark for stopping and reporting the position when a match is found
    • 1 mark for reporting that the target is absent if the end is reached without a match
  2. 2.Explain[3 marks]

    Explain how a bubble sort puts a list into ascending order.

    Show mark schemeHide mark scheme

    Model answer

    It compares each pair of neighbouring items in a pass and swaps any pair that is out of order. After each pass the next largest item is in its final place. It repeats passes until a pass makes no swaps.

    • 1 mark for comparing neighbouring items and swapping those in the wrong order
    • 1 mark for repeating passes so that the largest remaining item moves to the end
    • 1 mark for stopping when a pass makes no swaps
  3. 3.Determine[2 marks]

    Determine the list after the first pass of a bubble sort on 4, 2, 7, 1 in ascending order.

    Show mark schemeHide mark scheme

    Model answer

    Swap 4 and 2 to give 2, 4, 7, 1. Keep 4 and 7. Swap 7 and 1. The list is 2, 4, 1, 7.

    • 1 mark for comparing neighbouring pairs and swapping 4 and 2, then 7 and 1, while leaving 4 and 7 in place
    • 1 mark for giving the list 2, 4, 1, 7
  4. 4.Compare[3 marks]

    Compare linear search and binary search.

    Show mark schemeHide mark scheme

    Model answer

    Linear search works on unsorted lists, but binary search needs a sorted list. Linear search may need up to nnn comparisons. Binary search needs about log⁡2n\log_2 nlog2​n comparisons, so it is faster on long sorted lists.

    • 1 mark for stating that linear search works on unsorted lists but binary search needs a sorted list
    • 1 mark for stating that linear search may need up to nnn comparisons
    • 1 mark for stating that binary search needs about log⁡2n\log_2 nlog2​n comparisons, so it is faster on long sorted lists
  5. 5.Outline[2 marks]

    Outline why a trace table is useful when checking an algorithm.

    Show mark schemeHide mark scheme

    Model answer

    It records each variable’s value after every step, so the algorithm can be tested by hand. The first row with a wrong value shows where a fault lies.

    • 1 mark for stating that it records the value of each variable after each step
    • 1 mark for stating that it helps locate where a fault occurs
  6. 6.Calculate[1 mark]

    Calculate the largest number of comparisons a linear search needs on a list of 250 items.

    Show mark schemeHide mark scheme

    Model answer

    The worst case is 250 comparisons, when the target is last or absent.

    • 1 mark for giving 250

Practice this topic

10 quick-fire multiple-choice questions, easy to hard. Tap an answer to see if you're right and the worked explanation. (The written questions with mark schemes are under “Check your recall” above.)

0 right0 of 10 answered

Includes the 2 quick checks in the note above.

3.

Easy[1 mark]

Which statement about a trace table is correct?
Show answer and explanation

Answer: B · Worked explanation

A trace table is a testing aid. Each row shows the variable values after one step, so a person can follow the algorithm by hand. It does not store data for a search or count items, and sorting a list is the job of an algorithm such as bubble sort, not of a table that records what happens.
4.

Medium·Determine[1 mark]

A linear search looks for 12 in the list 5, 12, 8, 12, 3. Positions start at 0 and the search stops at the first match. Determine the position it returns.
Show answer and explanation

Answer: A · Worked explanation

Position 0 holds 5, which does not match. Position 1 holds 12, so the search stops and returns 1. The value 2 is the number of comparisons made, or the position if counting from 1. The value 3 is where the second 12 sits, but the search never reaches it.
5.

Medium·Determine[1 mark]

A bubble sort puts 6, 2, 5, 1 into ascending order. Determine the list after the first pass.
Show answer and explanation

Answer: D · Worked explanation

Swap 6 and 2 to give 2, 6, 5, 1. Swap 6 and 5 to give 2, 5, 6, 1. Swap 6 and 1 to give 2, 5, 1, 6. The fully sorted list 1, 2, 5, 6 needs further passes. The list 2, 6, 5, 1 shows only the first swap, not a complete pass.
6.

Medium·Calculate[1 mark]

An unsorted list holds 400 items. Calculate the largest number of comparisons a linear search needs.
Show answer and explanation

Answer: C · Worked explanation

The worst case occurs when the target is last or absent, so every one of the 400 items is compared once. The value 200 is only about half the list, which is not the worst case. The value 9 is roughly the count for a binary search, which needs a sorted list, and 4002400^24002 grows like a bubble sort.
7.

Medium·Calculate[1 mark]

A sorted list holds 1000 items. Which value is closest to the most comparisons a binary search needs?
Show answer and explanation

Answer: B · Worked explanation

Each comparison halves the remaining items: 1000 becomes about 500, 250, 125, 63, 32, 16, 8, 4, 2 and 1. That is about 10 steps, matching log⁡21000\log_2 1000log2​1000. The value 1000 is the linear search worst case, and 500 is roughly the average number of comparisons for a linear search, not the binary search worst case. The value 100 matches neither method.
8.

Hard·Predict[2 marks]

A bubble sort takes about 1 million comparisons on a list of 1000 items, and its work grows roughly with n2n^2n2. Predict the comparisons needed for 2000 items.
Show answer and explanation

Answer: A · Worked explanation

Work growing with n2n^2n2 means doubling nnn multiplies the work by 22=42^2=422=4, so 1 million becomes about 4 million. The value 2 million treats the growth as linear, which suits linear search rather than bubble sort. Eight million would need the work to grow with n3n^3n3.
9.

Hard·Determine[2 marks]

A bubble sort puts the list 4, 3, 2, 1 into ascending order. Determine the total number of swaps made before the list is sorted.
Show answer and explanation

Answer: D · Worked explanation

Pass 1 makes 3 swaps and gives 3, 2, 1, 4. Pass 2 makes 2 swaps and gives 2, 1, 3, 4. Pass 3 makes 1 swap and gives 1, 2, 3, 4. The total is 3+2+1=63+2+1=63+2+1=6. The value 3 counts only the swaps in the first pass.
10.

Hard·Compare[2 marks]

A student says binary search is always faster than linear search. Compare the two methods to judge the claim.
Show answer and explanation

Answer: C · Worked explanation

Binary search halves a sorted list each step, so it wins on long lists, but it fails on unsorted data and sorting first adds cost. Saying it works on any list ignores that requirement. Checking the middle item is binary search, not linear search, and correct results do not mean equal efficiency.

Keep going

Next topicB2.5 File processingPrevious topicB2.3 Programming constructs

More in B2 · Programming

  1. B2.1Programming fundamentalsNotes · 10 questions
  2. B2.2Data structuresNotes · 10 questions
  3. B2.3Programming constructsNotes · 10 questions
  4. B2.4Programming algorithmsNotes · 10 questions
  5. B2.5File processingNotes · 10 questions

All IB Computer Science topics →

Draft: written by Scribe and checked automatically, not yet by a subject reviewer.

Practice questions are original, written by Scribe and checked automatically for correctness.

Topic codes follow the official numbering. Not endorsed by IB Diploma Programme or any exam board.

On this page

0/6 read

  1. 1A linear search checks each item in turn
  2. 2A trace table lets you follow an algorithm by hand
  3. 3Bubble sort swaps neighbouring items until the list is ordered
  4. 4Tracing a bubble sort shows how each pass works
  5. 5Efficiency describes how the work grows with list size
  6. 6Binary search needs fewer comparisons but requires sorted data
  7. Check your recall
  8. Practice: 10 questions
All coursesScribeHow it worksPricingPrivacyTerms

Notes and questions are written by Scribe in our own words. Topic codes follow the official course numbering so you can find your place. Not produced or endorsed by the IB, College Board, AQA, OCR, Pearson Edexcel or any exam board.

© 2026 Scribe

Linear and binary search growth

Worst-case comparisons0102030405060700204060Number of items, n
  • Linear search
  • Binary search