01 | CORRECT IS THE FIRST REQUIREMENT

An algorithm is a precise method for solving a problem. Efficiency asks how much work or memory it needs. A quick method returning wrong answers is not a successful optimisation. Establish correctness and input assumptions first.

Input size, often called n, describes how much data the method receives. For searching a list, n is the number of items. For a text-processing task, it could be the number of characters. Define n before making a claim about growth.

A program’s observed time also depends on hardware, interpreter overhead and input arrangement. Counting selected operations helps reveal a pattern without pretending that one comparison always takes exactly the same number of seconds.

02 | COUNT A MEANINGFUL OPERATION

In a linear search of n items, an absent target requires n equality checks. A target at the first position needs one. The same algorithm therefore has different best and worst cases. You must say which case you are describing.

Binary search roughly halves its ordered interval after each unsuccessful inspection. Searching 1,024 positions takes at most 11 inspected midpoints in this inclusive-bound implementation, while an absent linear-search target inspects all 1,024.

This comparison assumes the data is already sorted and integer comparison is treated as one basic operation. Sorting a fresh list solely for one query adds work. Counting inspections excludes that preparation and the rest of the application.

def inspected_linear(values, target):
    checks = 0
    for value in values:
        checks += 1
        if value == target:
            return True, checks
    return False, checks

print(inspected_linear([2, 5, 8, 12], 2))
print(inspected_linear([2, 5, 8, 12], 99))

(True, 1)
(False, 4)

03 | BIG O DESCRIBES A GROWTH BOUND

Big O notation describes an asymptotic upper bound on growth, rather than an exact time or a stopwatch result. In these introductory comparisons, we use conventional bounds for the stated case and treat basic operations as constant cost.

O(1) work stays bounded independently of n, such as accessing a known list index under the usual model. O(n) grows linearly, as an absent linear search does. O(log n) grows slowly through repeated halving, as binary search does. O(n²) can arise when each of n passes does work proportional to n.

Constants and lower-order terms are omitted to focus on growth. This does not mean they never matter in practice. Two methods with the same Big O can have very different measured performance for the data you actually use.

The numbers illustrate functions 1, n and n², not exact instruction counts for all algorithms in those classes.

04 | NESTED LOOPS NEED A TRACE, NOT A GUESS

Two nested loops each ranging over n values perform n × n body executions. But nesting alone does not prove quadratic growth. An inner loop fixed at three repetitions performs 3n executions, which is O(n).

Bubble sort can require n(n - 1)/2 neighbouring comparisons in its worst case. Its shrinking inner loop still produces quadratic growth. With the early-exit version from 04.4, an already ordered list needs one linear pass.

Python’s built-in sorting has O(n log n) worst-case time in the usual comparison model and can exploit existing ordered runs. For application code, prefer that implementation over your educational bubble sort.

05 | TIME AND SPACE ARE DIFFERENT COSTS

Time complexity concerns work; space complexity concerns memory growth. State whether you mean total storage including input or auxiliary space, meaning additional working storage. A copied list requires extra storage even when its items are references to existing objects.

An iterative binary search keeps only a few bounds and therefore uses O(1) auxiliary space. A recursive implementation can create a stack frame per call. A function returning a new n-item list needs space for that output.

For very large integers, arithmetic itself is not constant cost. The simple models in this lesson are useful for learning control-flow growth, but a precise implementation analysis must account for its data representation too.

06 | RECURSION SOLVES A SMALLER VERSION

Recursion happens when a function calls itself, directly or indirectly. A safe recursive design needs a base case that returns without another recursive call and a step that moves valid input toward that base case.

Factorial of a non-negative integer multiplies the integers from one through n. By definition 0! is 1. For n > 0, factorial(n) = n × factorial(n - 1). This gives a smaller version of the same problem at every call.

The function below checks the supported input, including rejecting Boolean values even though bool is a subclass of int. raise ValueError creates a deliberate error for a caller to handle. It documents an invalid input rather than recursing endlessly through negative numbers.

def factorial(number):
    """Return factorial for a non-negative integer; small inputs only."""
    if type(number) is not int or number < 0:
        raise ValueError("Use a non-negative integer")
    if number == 0:
        return 1
    return number * factorial(number - 1)

print(factorial(4))
print(factorial(0))

24
1

07 | THE CALLS WAIT, THEN UNWIND

factorial(3) cannot complete 3 × factorial(2) until the inner call returns. It waits while factorial(2) waits for factorial(1), which waits for factorial(0). Each call has its own local number and place to resume.

The call stack records active calls. The base call returns 1. The waiting call for one calculates 1 × 1, the call for two calculates 2 × 1, and the call for three calculates 3 × 2. This return journey is called unwinding.

The recursive call is not a loop jumping back to overwrite one number. Several calls are active at once. Tracking separate stack frames explains why the earlier values remain available for the multiplications.

08 | RECURSION HAS LIMITS

This factorial uses O(n) calls and O(n) stack frames in the simple operation model. An iterative version uses a loop and O(1) auxiliary space for its accumulator, excluding the growing size of the integer result. Python does not eliminate these tail or waiting calls automatically.

Python has a recursion-depth limit and may raise RecursionError for deep recursion. Increasing that limit is not a good first response to a missing base case. Use small examples to learn and choose iteration for this straightforward calculation in ordinary code.

Recursion fits some naturally nested tasks, such as walking a small tree. It is not automatically faster. A naive recursive Fibonacci implementation repeatedly solves overlapping subproblems and can grow exponentially; that is a different structure from factorial’s one smaller call.

def factorial_iterative(number):
    if type(number) is not int or number < 0:
        raise ValueError("Use a non-negative integer")
    result = 1
    for factor in range(1, number + 1):
        result *= factor
    return result

print(factorial_iterative(4))

24

09 | FOLLOW DESCENT AND UNWINDING

Choose a small non-negative integer. The trace first creates waiting calls, reaches factorial(0), then resolves each result in reverse call order. Press the next-step button beneath the trace so it stays close to the latest operation.

10 | MAKE A REASONED CHOICE

Explain efficiency using a named input size, a stated case and a meaningful operation. Say what preparation is included. Comparing binary search to linear search without mentioning the sorting requirement can lead to an unsuitable design.

For recursion, identify the supported inputs, base case, progress step and stored waiting work. Trace zero, one and a small larger input. Test invalid inputs separately without running an intentionally unbounded broken function.

Clear reasoning is more useful than memorising complexity labels. Show why the loop count or interval reduction produces the growth you claim, then measure a real application if performance becomes important.

PUT YOUR SKILLS TO WORK

Use the Section 4 challenges to practise these ideas independently. Work in your Python editor, predict results and keep a short test record.