Two correct programs can differ enormously in speed. Counting the steps an algorithm needs as the input grows is how we compare them.
📐 Counting steps
We describe growth with Big-O notation: how the number of steps grows with input size n.
O(1) constant reading list[5]
O(log n) logarithmic binary search
O(n) linear linear search, summing a list
O(n²) quadratic bubble sort, nested loops
n = 1000:
linear search ≤ 1000 steps
binary search ≤ 10 steps
🖼️ See it
Quadratic algorithms slow down dramatically as the input grows; logarithmic ones barely notice.
🧮 Nested loops
A loop inside a loop multiplies the work: an outer loop of n and an inner loop of n gives n² steps. Doubling n makes an O(n²) algorithm four times slower.
for i in 1..n: for j in 1..n: step
n = 10 → 100 steps
n = 20 → 400 steps (4 times more)
n = 1 000 000 and log₂ n ≈ 20:
binary search needs about 20 steps
Choose the better algorithm before tuning code. A faster algorithm beats a faster computer.
✏️ Quick check · 1 of 7
Big-O
Big-O notation describes:
Growth.
✏️ Quick check · 2 of 7
Binary search
Binary search has complexity:
Halving.
✍️ Type your answer · 3 of 7
Two nested loops each run n = 10 times.
How many times does the inner body run?
Enter an exact answer, without rounding.
Multiply.
✍️ Type your answer · 4 of 7
The same nested loops run with n = 20.
How many times does the inner body run?
Enter an exact answer, without rounding.
Multiply.
✍️ Type your answer · 5 of 7
An O(n²) algorithm takes 3 s for n = 1000. The input is doubled.
How many seconds does it take now?
Enter an exact answer, without rounding.
s
Square the factor.
✍️ Type your answer · 6 of 7
A sorted list holds 1 000 000 items (2²⁰ ≈ 1 000 000).
About how many steps does a binary search take at most?
Enter an exact answer, without rounding.
How many halvings?
✍️ Type your answer · 7 of 7
A linear search checks every item in a list of 500.
What is the worst-case number of comparisons?
Enter an exact answer, without rounding.
Check all.
📝 Lesson quiz · 5 questions
0 / 5
Re-read the lesson, then give it another go.
Question 1 of 5
Which is the slowest as n grows large?
Question 2 of 5
Reading list[5] has complexity:
Question 3 of 5
Worst case means:
Question 4 of 5
Which is more important for large data?
Question 5 of 5
Space complexity measures:
Lesson 2 · Algorithms
🪆 Recursion
A recursive function solves a problem by calling itself on a smaller version of the same problem, until it reaches a case it can answer directly.
♾️ Base case and recursive case
Every recursive function needs a base case (stops the recursion) and a recursive case (a call on a smaller input). Without a base case it never ends.
function fact(n):
if n <= 1: return 1
return n * fact(n - 1)
fact(4) = 4 · fact(3) = 4 · 3 · fact(2) = 4 · 3 · 2 · 1 = 24
fact(5) = 120
🖼️ See it
Calls stack up until the base case; then the answers return: 1, 2, 6, 24.
🌀 More examples
Fibonacci: each term is the sum of the two before it. Recursion also fits tree-like data and “divide and conquer”.
Positions start at 0 from the left and −1 from the right. The slice s[1:4] takes positions 1, 2 and 3 and stops before 4: "YTH".
💾 Reading and writing files
Open a file in read, write (replaces content) or append mode, then close it. Always handle the case where the file does not exist.
file "scores.txt" has 5 lines: 12, 7, 9, 20, 2
read each line, convert to int, add up
total = 12 + 7 + 9 + 20 + 2 = 50
average = 50 / 5 = 10
mode "w" overwrites; mode "a" adds to the end
Close files (or use a with-block) so data is saved and the file is released.
✏️ Quick check · 1 of 7
Write mode
Opening a file in write mode:
Overwrite.
✏️ Quick check · 2 of 7
Index
In "Computer", the character at index 3 is:
Count from 0.
✍️ Type your answer · 3 of 7
s = "Computer".
What is len(s)?
Enter an exact answer, without rounding.
Count the letters.
✍️ Type your answer · 4 of 7
"a,b,c,d" is split on commas.
How many items are in the resulting list?
Enter an exact answer, without rounding.
Count the parts.
✍️ Type your answer · 5 of 7
A file has the lines 12, 7, 9, 20 and 2.
What is their total?
Enter an exact answer, without rounding.
Add them.
✍️ Type your answer · 6 of 7
The same file has 5 lines totalling 50.
What is the average?
Enter an exact answer, without rounding.
Total ÷ count.
✍️ Type your answer · 7 of 7
A word is stored in s = "banana".
How many times does the letter "a" appear?
Enter an exact answer, without rounding.
Count them.
📝 Lesson quiz · 5 questions
0 / 5
Re-read the lesson, then give it another go.
Question 1 of 5
Which operation joins two strings?
Question 2 of 5
Why should you close a file?
Question 3 of 5
s[0:3] of "Computer" is:
Question 4 of 5
Append mode:
Question 5 of 5
Input from a file is usually read as:
Lesson 4 · Coding
🧱 Object-Oriented Programming
Object-oriented programming bundles data and the actions on it into objects, which mirror things in the real world and make big programs easier to manage.
📦 Classes and objects
A class is a blueprint. An object (instance) is one thing built from it. A class has attributes (data) and methods (actions).
class Account:
balance = 0
method deposit(x): balance = balance + x
method withdraw(x): balance = balance - x
a = Account()
a.deposit(100); a.withdraw(30)
a.balance = 70
🖼️ See it
One class can make many objects. Each object has the same methods but its own attribute values.
🧬 The big ideas
Encapsulation keeps data private behind methods. Inheritance lets a new class reuse an existing one. Polymorphism lets different classes respond to the same method in their own way.
class Animal: speak()
class Dog extends Animal: speak() → "Woof"
class Cat extends Animal: speak() → "Meow"
3 Dog objects + 2 Cat objects = 5 objects
but only 3 classes
Use objects to model nouns in your problem (Student, Account) and methods for the verbs.
✏️ Quick check · 1 of 7
Class
A class is:
Plan.
✏️ Quick check · 2 of 7
Inheritance
Inheritance allows a class to:
Reuse.
✏️ Quick check · 3 of 7
Encapsulation
Encapsulation means:
Hidden.
✍️ Type your answer · 4 of 7
An account starts at 0. deposit(100) then withdraw(30).
What is the balance?
Enter an exact answer, without rounding.
Apply in order.
✍️ Type your answer · 5 of 7
A program makes 3 Dog objects and 2 Cat objects.
How many objects exist?
Enter an exact answer, without rounding.
Add them.
✍️ Type your answer · 6 of 7
A program defines the classes Animal, Dog and Cat.
How many classes are there?
Enter an exact answer, without rounding.
Count the blueprints.
✍️ Type your answer · 7 of 7
A Student class has the attributes name, age and grade.
How many attributes does each Student object hold?
Enter an exact answer, without rounding.
Count them.
📝 Lesson quiz · 5 questions
0 / 5
Re-read the lesson, then give it another go.
Question 1 of 5
An object is:
Question 2 of 5
A method is:
Question 3 of 5
Polymorphism lets:
Question 4 of 5
Which is an attribute of a Car class?
Question 5 of 5
Private attributes are accessed via:
Lesson 5 · Hardware
🧠 The CPU & Computer Architecture
The CPU repeats one cycle billions of times a second. Understanding it explains why some computers are faster than others.
🔁 Fetch–decode–execute
The CPU fetches an instruction from memory, decodes it and executes it. Key parts: the ALU (arithmetic and logic), the control unit, registers and the program counter, which holds the address of the next instruction.
clock speed: 3 GHz = 3 000 000 000 cycles per second
1 instruction per cycle → 3 billion instructions per second
4 cores at the same speed can do up to
4 · 3 = 12 billion instructions per second
🖼️ See it
The CPU repeats this billions of times per second.
📦 Memory and storage
Cache is tiny, very fast memory inside the CPU. RAM is larger and slower, and storage is larger and slower still. More cache and RAM reduce waiting.
speed (fast → slow): registers, cache, RAM, SSD, hard disk
size (small → big): registers, cache, RAM, SSD, hard disk
an SSD has no moving parts and is faster than a hard disk
memory address of the next instruction: program counter + 1
More cores only help if the software can split its work across them.
✏️ Quick check · 1 of 7
Program counter
The program counter holds:
Next.
✏️ Quick check · 2 of 7
ALU
The ALU performs:
Maths and logic.
✏️ Quick check · 3 of 7
Cache
Cache memory is used to:
Close and fast.
✍️ Type your answer · 4 of 7
A CPU runs at 3 GHz and does 1 instruction per cycle.
How many billion instructions per second?
Enter an exact answer, without rounding.
One per cycle.
✍️ Type your answer · 5 of 7
Four cores each run at 3 GHz with 1 instruction per cycle.
What is the maximum in billions of instructions per second?
Enter an exact answer, without rounding.
Multiply.
✍️ Type your answer · 6 of 7
The program counter holds 100 and the instruction is 1 word long.
What address does it hold after the fetch?
Enter an exact answer, without rounding.
It moves to the next one.
✍️ Type your answer · 7 of 7
A clock speed of 2 GHz means this many billion cycles per second:
Give the number.
Enter an exact answer, without rounding.
Giga = billion.
📝 Lesson quiz · 5 questions
0 / 5
Re-read the lesson, then give it another go.
Question 1 of 5
The correct order of the CPU cycle is:
Question 2 of 5
Which is the fastest memory?
Question 3 of 5
A core is:
Question 4 of 5
Embedded systems are:
Question 5 of 5
A GPU is especially good at:
Lesson 6 · Data
➖ Binary Arithmetic & Negative Numbers
Computers add in binary, represent negative numbers using two’s complement, and can overflow when a result does not fit.
➕ Binary addition
Binary addition follows 4 rules: 0+0 = 0, 0+1 = 1, 1+1 = 10 (write 0, carry 1), and 1+1+1 = 11. A result that needs more bits than are available causes overflow.