B1 Computational thinking & algorithms (searching, sorting, Big-O) – IB Computer Science exam questions with mark scheme

1Core4 marks

A sorted list is stored as data = [3, 8, 12, 19, 25, 31, 40, 47] (indices 0 to 7). A binary search looks for the value 31. Count each examination of a middle item as one comparison. The midpoint is calculated as mid = (low + high) // 2, starting with low = 0 and high = 7.

(a) State the value of mid and the item examined in the first comparison. [2]

(b) Show how low and high change, and state how many comparisons are needed to find 31. [2]

First mid = (0 + 7) // 2 = 3(1)
Item examined is data[3] = 19(1)
19 < 31 so the lower half is discarded: low becomes 4 (high stays 7); second mid = 5 gives data[5] = 31(1)
Found after 2 comparisons(1)
Answer: (a) mid = 3, item 19. (b) low = 4, high = 7; 2 comparisons.
Examiner tip: Show the midpoint calculation; students often forget to move low to mid + 1 and instead set low = mid.

2Standard4 marks

A bubble sort with a swapped flag is applied to [5, 2, 9, 1, 6]. In each pass adjacent items are compared from left to right and swapped if out of order. The algorithm stops after a pass in which no swap occurs.

(a) Write down the list after the first pass. [1]

(b) State the number of swaps made in the first pass. [1]

(c) Determine the total number of passes the algorithm makes, including the final pass. Show the list after each pass. [2]

After pass 1: [2, 5, 1, 6, 9](1)
3 swaps in pass 1 (5↔2, 9↔1, 9↔6)(1)
Pass 2 gives [2, 1, 5, 6, 9] and pass 3 gives [1, 2, 5, 6, 9] (list sorted after pass 3)(1)
Pass 4 makes no swaps so the algorithm stops: 4 passes in total(1)
Answer: (a) [2, 5, 1, 6, 9] (b) 3 (c) 4 passes
Examiner tip: The extra pass with no swaps is needed to detect that the list is sorted; many students stop at 3.

3Standard4 marks

State the time complexity in Big-O notation of each code fragment, where n = len(items).

(a)

for i in range(n):
    for j in range(n):
        count += 1

[1]

(b)

i = n
while i > 1:
    i = i // 2

[1]

(c)

total = 0
for x in items:
    total += x

[1]

(d) Outline why the fragment in (b) is much more efficient than the fragment in (c) for very large n. [1]

(a) O(n²) (accept O(n^2), O(n*n))(1)
(b) O(log n) (accept O(log₂ n))(1)
(c) O(n)(1)
(d) In (b) i is halved each iteration, so the number of steps grows very slowly (about log₂ n, e.g. about 20 for a million) whereas in (c) the number of steps grows in direct proportion to n(1)
Answer: (a) O(n²) (b) O(log n) (c) O(n)
Examiner tip: Name the halving pattern for log n; saying 'it is faster' without relating step count to n earns nothing.

4Core4 marks

A company is designing a mobile app that shows the quickest bus route between two stops in a city.

(a) Explain how abstraction could be used when designing the app's route map. [2]

(b) Explain how decomposition could be used when developing the app. [2]

Abstraction: removes unnecessary detail such as building shapes, road widths and shop names (accept any sensible irrelevant detail for this app)(1)
Keeping only the relevant features, e.g. stops as nodes and journey times between them (a graph), so the route can be calculated more simply / efficiently(1)
Decomposition: break the problem into smaller sub-problems, e.g. finding nearby stops, calculating the route, displaying the map, handling live bus times (accept any sensible sub-problems in context)(1)
Each sub-problem can be designed, coded and tested separately (possibly by different team members) and then combined(1)
Answer: Abstraction: hide irrelevant detail, model stops/times as a graph. Decomposition: split into smaller manageable components.
Examiner tip: Always apply the term to the scenario given; generic definitions alone score at most half marks.

5Hard5 marks

A sorted list holds 1000 customer ID numbers.

(a) State the maximum number of comparisons a linear search needs. [1]

(b) Calculate the maximum number of comparisons a binary search needs, counting one comparison for each item examined. Show your working. [2]

(c) The list is replaced by an unsorted list of 1000 IDs. Explain why binary search cannot be used on this list, and why sorting it with selection sort just to carry out one search would not be worthwhile. [2]

(a) 1000 comparisons (item is last or absent)(1)
(b) Each comparison halves the list: 1000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1 (ten list sizes), or uses ⌊log₂ 1000⌋ + 1, or 2⁹ = 512 < 1000 ≤ 1024 = 2¹⁰(1)
Maximum = 10 comparisons(1)
(c) Binary search relies on the data being in order so that half of it can be discarded after each comparison; in an unsorted list the discarded half could contain the target(1)
Selection sort is O(n²) (about 1000 × 999 ÷ 2 = 499 500 comparisons), far more than the at most 1000 comparisons (O(n)) of a linear search, so one linear search is cheaper(1)
Answer: (a) 1000 (b) 10 (c) binary search needs sorted data; selection sort is O(n²) (≈ 500 000 comparisons), far more than one O(n) linear search (≤ 1000).
Examiner tip: Give the number 10, not just 'log n'; show the halving sequence or the log₂ calculation.

6Hard6 marks

Two algorithms check whether a list of n integers contains duplicates. Every integer in the list is between 0 and 99 999.

Algorithm A

def has_dup_a(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

Algorithm B

def has_dup_b(nums):
    seen = [False] * 100000
    for x in nums:
        if seen[x]:
            return True
        seen[x] = True
    return False

(a) State the worst-case time complexity of Algorithm A and justify your answer. [2]

(b) Calculate the number of comparisons nums[i] == nums[j] Algorithm A makes in the worst case when n = 10 000. [1]

(d) Describe one disadvantage of Algorithm B compared with Algorithm A. [1]

(e) Identify which algorithm you would recommend for n = 10 000 and give a reason. [1]

(a) O(n²)(1)
Nested loops: each item is compared with every later item, giving n(n−1)/2 comparisons, which grows with n²(1)
(b) 10 000 × 9 999 ÷ 2 = 49 995 000 comparisons (worst case: no duplicates)(1)
(c) O(n) (accept O(n + k) where k = 100 000 is the size of the seen list)(1)
(d) It uses a large amount of extra memory (a list of 100 000 Booleans) whatever the size of n, whereas A uses O(1) extra space; accept: it only works when the values lie in a known, limited range(1)
(e) Algorithm B, because about 10 000 loop iterations (plus creating a 100 000-item list) is far fewer than about 50 million comparisons; the extra memory is acceptable(1)
Answer: (a) O(n²) (b) 49 995 000 (c) O(n) (d) uses a large fixed block of extra memory / only works for a known value range (e) B
Examiner tip: In (a) a bare 'O(n²)' scores 1; the second mark needs the link to the nested loops.

Still losing marks on this topic?

Book a free introductory session and we'll find exactly which step is costing you.

Book a free intro