Arrays, dictionaries, searching, sorting and Big O: WACE Computer Science Unit 3

Syllabus dot point

“Use arrays and dictionaries, apply linear and binary search and standard sorting algorithms (such as bubble, selection and insertion sort), and compare algorithm efficiency using Big O notation”

WACEComputer ScienceUnit 3: Programming8 min readUpdated 23 Sep 2026

Quick answer

Arrays store ordered data accessed by index; dictionaries store key-value pairs with fast lookup. Linear search is O(n) and works on any list; binary search is O(log n) but needs sorted data. Bubble, selection and insertion sorts are O(n²). Big O compares how algorithms scale as data grows.

Jump to a section

What this dot point is asking
The answer
Practice questions

What this dot point is asking

You need to use two core data structures (arrays and dictionaries), apply standard searching and sorting algorithms, trace them, and compare their efficiency using Big O notation.

The answer

Data structures

Array (list): ordered, indexed elements. Fast access by index; inserting in the middle requires shifting elements. Two-dimensional arrays store tables.
Dictionary (associative array, hash map): key-value pairs. Very fast lookup by key (average O(1)); keys must be unique.

Searching

Linear search: check each element in turn until found or the end is reached. Works on any list. O(n).
Binary search: on a sorted list, compare with the middle element and discard half each time. O(log n).

Sorting

Algorithm	How it works	Worst case
Bubble sort	Repeatedly compare adjacent pairs and swap if out of order; largest values "bubble" to the end	O(n²)
Selection sort	Find the smallest remaining element and swap it into the next position	O(n²)
Insertion sort	Take each element and insert it into its correct place in the sorted part	O(n²), but fast on nearly sorted data

Big O notation

Big O describes how the number of steps grows as input size $n$ grows (usually the worst case).

Common complexities, fastest to slowest

$O(1)$ constant: dictionary lookup, array access by index.
$O(\log n)$ logarithmic: binary search.
$O(n)$ linear: linear search, a single loop.
$O(n^2)$ quadratic: nested loops, bubble, selection and insertion sort.

For 1000 items: O(log n) is about 10 steps, O(n) is 1000, O(n²) is 1 000 000.

Worked example

Selection sort on [29, 10, 14, 37]:

Smallest is 10; swap with 29: [10, 29, 14, 37].
Smallest of remaining is 14; swap with 29: [10, 14, 29, 37].
Smallest of remaining is 29; already in place: [10, 14, 29, 37].
Done. Three passes for four items; comparisons grow roughly with $n^2/2$ .

Common traps

Using binary search on unsorted data: It gives wrong results.
Miscalculating mid: Use integer division: (low + high) DIV 2.
Saying Big O measures seconds: It measures growth in steps as input grows.

Practice questions

Original practice questions graded from foundation to exam level, each with a full worked solution. Try them before revealing the solution.

foundation3 marks

Show the list [7, 3, 9, 2] after each pass of bubble sort (ascending).

Show worked solution →

Pass 1: compare and swap adjacent pairs: [3, 7, 9, 2] then [3, 7, 9, 2] then [3, 7, 2, 9]
Pass 2: [3, 7, 2, 9] then [3, 2, 7, 9]
Pass 3: [2, 3, 7, 9]

Final sorted list: [2, 3, 7, 9].

Marking guide: 1 mark per correct pass.

core4 marks

Trace a binary search for 41 in [5, 12, 19, 23, 34, 41, 56, 70], showing low, high and mid at each step (use integer division for mid).

Show worked solution →

Step	low	high	mid	list[mid]	Action
1	0	7	3	23	41 > 23, so low = 4
2	4	7	5	41	Found at index 5

Found at index 5 in 2 comparisons. A linear search would need 6 comparisons.

Marking guide: 1 mark per correct step, 1 mark for the result, 1 mark for comparing with linear search.

exam5 marks

A school's student database has 2000 records. Compare linear and binary search for finding a student by ID, using Big O and the maximum number of comparisons, and state when each is appropriate.

Show worked solution →

Linear search, O(n): checks records one by one; up to 2000 comparisons in the worst case. Works on unsorted data.
Binary search, O(log n): halves the search space each step; at most about 11 comparisons, because 2 to the power of 11 is 2048, which is more than 2000. Requires sorted data.
When to use: binary search suits frequent searches of large, sorted data (IDs in order). Linear search suits small or unsorted lists, or when data changes so often that keeping it sorted costs more than it saves. A dictionary keyed by ID would give O(1) average lookup.

Marking guide: 1 mark for each Big O, 1 mark for each worst-case count, 1 mark for appropriate use.

core4 marks

Show the list [8, 5, 6, 2, 9] after each pass of insertion sort (ascending), where each pass inserts the next unsorted element into its correct place in the sorted part.

Show worked solution →

The sorted part starts as [8]. Each pass takes the next element and shifts larger sorted elements one place right until the gap is in the correct position.

Pass 1: insert 5; 8 shifts right: [5, 8, 6, 2, 9]
Pass 2: insert 6; 8 shifts right, 5 stays: [5, 6, 8, 2, 9]
Pass 3: insert 2; 8, 6 and 5 all shift right: [2, 5, 6, 8, 9]
Pass 4: insert 9; it is larger than 8, so nothing moves: [2, 5, 6, 8, 9]

Final sorted list: [2, 5, 6, 8, 9] after 4 passes (n minus 1 passes for n = 5 items).

Marking guide: 1 mark per correct pass (4 marks).

exam5 marks

A school canteen app stores about 300 menu items and their prices. The developer is choosing between (i) two parallel arrays, names and prices, where prices[i] is the price of names[i], and (ii) a dictionary, prices, with the item name as the key. (a) Compare the two options for finding the price of one item, using Big O notation. (2 marks) (b) Write pseudocode or Python for a function orderTotal(order, prices) that takes a list of item names and the dictionary, and returns the total cost. State the total for the order ["pie", "juice", "pie"] when pie costs 4.50 dollars and juice costs 3.20 dollars. (3 marks)

Show worked solution →

(a) With parallel arrays, the program must linear search names to find the index of the item, then read prices at that index. In the worst case it checks all 300 names, so lookup is O(n). With a dictionary, the name is the key, so the price is found directly by key with O(1) average lookup, however many items there are. The dictionary is faster and simpler, and it keeps each name joined to its price.

(b)

def order_total(order, prices):
    total = 0
    for item in order:
        total = total + prices[item]
    return total

For ["pie", "juice", "pie"]: 4.50 + 3.20 + 4.50 = 12.20 dollars. The loop runs once per item in the order, and each dictionary lookup is O(1) on average.

Marking guide: (a) 1 mark for O(n) with parallel arrays and why, 1 mark for O(1) average with a dictionary. (b) 1 mark for looping over the order, 1 mark for accumulating the price looked up by key and returning it, 1 mark for the correct total of 12.20 dollars.

exam14 marks

A medical clinic's booking app stores the patient IDs for today's appointments. Sorted list: [104, 118, 125, 131, 142, 157, 163, 170, 188, 196] (indexes 0 to 9). (a) Trace a binary search for patient ID 120, showing low, high, mid and list[mid] at each step (use integer division for mid), and state the result. (4 marks) (b) A second list of waiting times, [63, 17, 45, 8, 29], must be sorted in ascending order. Show the list after each pass of selection sort. (4 marks) (c) The clinic's full patient file holds 5000 IDs in sorted order. State the maximum number of comparisons needed to find one ID using linear search and using binary search, and show how you worked out the binary search figure. (3 marks) (d) The receptionist mostly looks up one patient at a time by ID. Recommend whether to store the patients in a sorted array or a dictionary keyed by patient ID, and justify your answer using Big O notation. (3 marks)

Show worked solution →

(a)

Step	low	high	mid	list[mid]	Action
1	0	9	4	142	120 < 142, so high = 3
2	0	3	1	118	120 > 118, so low = 2
3	2	3	2	125	120 < 125, so high = 1
4	2	1			low > high, so stop

Result: 120 is not in the list, found after 3 comparisons.

(b) Each pass finds the smallest remaining value and swaps it into the next position.

Pass 1: smallest is 8; swap with 63: [8, 17, 45, 63, 29]
Pass 2: smallest remaining is 17; already in place: [8, 17, 45, 63, 29]
Pass 3: smallest remaining is 29; swap with 45: [8, 17, 29, 63, 45]
Pass 4: smallest remaining is 45; swap with 63: [8, 17, 29, 45, 63]

(c) Linear search: up to 5000 comparisons (the ID may be last or absent). Binary search halves the search space each comparison. 2 to the power of 12 is 4096, which is less than 5000, and 2 to the power of 13 is 8192, which is more than 5000, so at most 13 comparisons are needed.

(d) Recommend a dictionary keyed by patient ID. Looking up a key in a dictionary is O(1) on average, so each lookup takes about the same time however many patients there are. A sorted array allows binary search, which is O(log n) (up to 13 comparisons for 5000 IDs), and the array must also be kept sorted when new patients are added, which requires shifting elements. Since the main task is single lookups by a unique ID, the dictionary is the more efficient choice.

Marking guide: (a) 1 mark for each of the first three correct steps, 1 mark for stopping when low > high and stating not found (4 marks). (b) 1 mark per correct pass (4 marks). (c) 1 mark for 5000, 1 mark for 13, 1 mark for the powers of 2 reasoning (3 marks). (d) 1 mark for recommending the dictionary, 1 mark for O(1) average lookup, 1 mark for contrasting with O(log n) binary search or the cost of keeping the array sorted (3 marks). Total 14 marks.

exam18 marks

A sports club app keeps members' scores and names. (a) Show the list [4, 1, 3, 9, 7] after each swap and after each pass of bubble sort (ascending). Each pass compares one fewer pair than the previous pass, and the sort stops after a pass with no swaps. State the total number of comparisons and swaps. (5 marks) (b) Bubble sort is O(n squared). If the app takes 0.2 seconds to bubble sort 1000 scores, estimate the time for 2000 scores and for 10 000 scores, and explain your reasoning. (3 marks) (c) Write pseudocode or Python for a function countNames(names) that takes a list of member names and returns a dictionary giving how many times each name appears. State the Big O of your function. (5 marks) (d) After new scores are added, the list is often nearly sorted, for example [2, 3, 5, 4, 6]. Count the comparisons insertion sort makes on this list, state how many comparisons selection sort makes on it, and explain why insertion sort is a good choice for nearly sorted data. (5 marks)

Show worked solution →

(a)

Pass 1 (4 comparisons):

Compare 4 and 1: swap, giving [1, 4, 3, 9, 7]
Compare 4 and 3: swap, giving [1, 3, 4, 9, 7]
Compare 4 and 9: no swap
Compare 9 and 7: swap, giving [1, 3, 4, 7, 9]

After pass 1: [1, 3, 4, 7, 9]

Pass 2 (3 comparisons): 1 and 3, 3 and 4, 4 and 7; no swaps, so the sort stops. After pass 2: [1, 3, 4, 7, 9]

Total: 7 comparisons and 3 swaps.

(b) For O(n squared), the number of steps grows with the square of n. Doubling n from 1000 to 2000 multiplies the steps by 2 squared = 4, so about 0.2 x 4 = 0.8 seconds. Multiplying n by 10 multiplies the steps by 10 squared = 100, so about 0.2 x 100 = 20 seconds. These are estimates, because Big O describes growth in steps, not exact times.

(c)

def count_names(names):
    counts = {}
    for name in names:
        if name in counts:
            counts[name] = counts[name] + 1
        else:
            counts[name] = 1
    return counts

For example, ["Ari", "Bea", "Ari", "Cal", "Bea", "Ari"] returns {"Ari": 3, "Bea": 2, "Cal": 1}.

Big O: O(n). The loop runs once per name, and each dictionary check and update is O(1) on average.

(d) Insertion sort on [2, 3, 5, 4, 6]:

Insert 3: compare with 2, no shift (1 comparison)
Insert 5: compare with 3, no shift (1 comparison)
Insert 4: compare with 5, shift 5; compare with 3, stop (2 comparisons)
Insert 6: compare with 5, no shift (1 comparison)

Total: 5 comparisons (and 1 shift). Selection sort always scans the whole unsorted part to find the smallest value, so it makes 4 + 3 + 2 + 1 = 10 comparisons whatever the order of the data.

Insertion sort stops each pass as soon as it finds an element smaller than the one being inserted. When the data is nearly sorted, most elements need only one comparison, so the work is close to one pass through the list (close to linear). Its worst case is still O(n squared), but on nearly sorted data it does far less work than selection sort.

Marking guide: (a) 2 marks for correct swaps and list after pass 1, 1 mark for pass 2 with no swaps and stopping, 1 mark for 7 comparisons, 1 mark for 3 swaps (5 marks). (b) 1 mark for 0.8 seconds, 1 mark for 20 seconds, 1 mark for explaining the square relationship (3 marks). (c) 1 mark for creating an empty dictionary, 1 mark for looping over the names, 1 mark for adding a new key with count 1, 1 mark for incrementing an existing key and returning the dictionary, 1 mark for O(n) (5 marks). (d) 2 marks for 5 comparisons with working, 1 mark for 10 comparisons for selection sort, 2 marks for explaining why insertion sort does little work on nearly sorted data (5 marks). Total 18 marks.

Practise this

Sources & how we know this

Computer Science ATAR course: syllabus and support materials — SCSA
Computer Science: past ATAR course examinations — SCSA