Topic 4 is the heart of the course: the thinking skills behind problem solving, how to express solutions as algorithms, the standard searching and sorting algorithms, and how we measure algorithm efficiency with Big-O.
Work through each screen, answer the questions as you go (some are wordy, some are calculations) and collect ⭐ stars. Press Start when you are ready.
Thinking ahead — identify inputs, outputs and pre-conditions in advance.
Thinking procedurally — order the steps correctly.
Thinking logically — reason about decisions and conditions.
Thinking concurrently — spot steps that can happen at the same time.
Decompose
Decomposition and pattern recognition
Decomposition breaks a large problem into smaller sub-problems that are easier to solve. Pattern recognition spots similarities so one solution can be reused. Abstraction then keeps only the details that matter.
Quick check
Abstraction
?A map of a train network shows only stations and connections, not the exact geography. This is an example of:
Algorithms
Algorithms, flowcharts and pseudocode
An algorithm is a finite, ordered set of unambiguous steps that solves a problem. We express algorithms as flowcharts (boxes for process, diamonds for decisions) or as pseudocode. Programs then use variables, collections/arrays and subprograms (reusable named blocks).
Search
Searching algorithms
Two standard searches:
Linear (sequential) search — check each item in turn. Works on any list; worst case checks every element.
Binary search — repeatedly halve a sorted list, discarding half each time. Much faster, but the data must already be sorted.
Quick check
Which search needs sorted data?
?Which searching algorithm only works correctly if the data is already sorted?
Calculate
Binary search cost
1Binary search halves the list each step, so the maximum number of comparisons for n items is the floor of log base 2 of n, plus 1. For n = 1024 items, what is that maximum?
comparisons
Hint: 2 to the power 10 is 1024, so log base 2 of 1024 is 10; add 1.
Sort
Sorting algorithms
Two standard sorts:
Bubble sort — repeatedly compare adjacent items and swap if out of order; large values bubble to the end.
Selection sort — repeatedly find the smallest remaining item and place it next.
Both compare pairs. In the worst case each does about n times n over 2 comparisons, which is order n squared.
Calculate
Bubble sort comparisons
2A bubble sort on 6 items makes n times (n minus 1), all divided by 2, comparisons in the worst case. How many comparisons is that for n = 6?
comparisons
Hint: 6 times 5 is 30, divided by 2.
Sort it
Search, sort or construct?
Tap an item, then the category it belongs to.
🔄 Sorting algorithm
🔍 Searching algorithm
🧱 Programming construct
Efficiency
Algorithm efficiency and Big-O
Big-O describes how the work grows as the input size n grows:
O(1) — constant: array access by index.
O(log n) — logarithmic: binary search.
O(n) — linear: linear search.
O(n^2) — quadratic: bubble and selection sort.
Quick check
Big-O of linear search
?What is the time complexity of a linear (sequential) search of n items?
Match it
Match the Big-O
Tap an algorithm on the left, then its Big-O complexity.
Algorithm
Complexity
Trace
Flowcharts and trace tables
A flowchart shows an algorithm graphically: rectangles for processes, diamonds for decisions, parallelograms for input and output. A trace table records how each variable changes as you step through the code, which is a key way to test and debug an algorithm by hand.
Quick check
Flowchart symbol
?In a flowchart, which symbol represents a decision (a yes/no question)?
Calculate
Linear search worst case
3In the worst case, a linear (sequential) search of a list of 200 items checks how many elements?
elements
Hint: linear search may have to check every element once.