Big O Notation: What A-Level CS Actually Expects

La notazione Big O appare in ogni major spec di informatica A-level (AQA, OCR, Edexcel) e confonde molti studenti non perché la matematica sia difficile, ma perché non la vedono mai collegata a codice vero. Questo è un percorso pratico su quello che devi sapere e come rispondere alle domande d'esame senza girarci intorno.

Cosa misura davvero Big O

Big O descrive come il tempo di esecuzione (o l'uso di memoria) di un algoritmo cresce al crescere della dimensione dell'input, solitamente chiamata n. Non è una misurazione al cronometro in secondi. È un modo di descrivere il tasso di crescita così puoi confrontare algoritmi indipendentemente dall'hardware.

Quando scrivi O(n), stai dicendo: se raddoppio l'input, il lavoro all'incirca raddoppia. O(n²) significa che raddoppiare l'input all'incirca quadruplica il lavoro. Questa relazione è quello che gli esaminatori vogliono che tu identifichi, non i conteggi esatti delle operazioni.

Le complessità che devi conoscere perfettamente

Per A-level, queste sono quelle che tornano ancora e ancora:

• O(1) – tempo costante. Accedere a un elemento di un array per indice: arr[5]. Non importa quanto sia grande l'array.
• O(log n) – logaritmico. Ricerca binaria su una lista ordinata. Ogni passo dimezza lo spazio di ricerca rimanente.
• O(n) – lineare. Un singolo loop attraverso una lista, come una ricerca lineare che controlla ogni elemento una volta.
• O(n log n) – linearitmico. Merge sort e quicksort (caso medio) rientrano qui.
• O(n²) – quadratico. Loop annidati sugli stessi dati, che è esattamente quello che bubble sort, insertion sort e selection sort fanno.
• O(2ⁿ) – esponenziale. Fibonacci ricorsivo ingenuo senza memoisation. Diventa brutto velocemente.

Dovresti essere in grado di guardare pseudocodice e dire quale di questi sia a prima vista, perché è principalmente quello che viene testato.

Leggere il codice per la complessità

Il metodo che funziona sempre: conta i loop e vedi come si relazionano a n.

# O(n) - un loop, un passaggio
for i in range(n):
    print(i)

# O(n^2) - loop annidato, entrambi legati a n
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - lo spazio di ricerca dimezza a ogni iterazione
low, high = 0, n - 1
while low <= high:
    mid = (low + high) // 2
    if target == arr[mid]:
        break
    elif target < arr[mid]:
        high = mid - 1
    else:
        low = mid + 1

Un loop annidato dove la portata del loop interno dipende da n è comunque O(n²), anche se sembra leggermente diverso (come for j in range(i) invece di for j in range(n) — è comunque quadratico complessivamente, solo con una differenza nel fattore costante).

Attento ai loop che non dipendono affatto da n. Un loop che gira sempre 10 volte indipendentemente dalla dimensione dell'input è O(1), anche se c'è un loop presente. Agli esaminatori piace nascondere questo.

Algoritmi di ordinamento comuni e il loro Big O

Questo è un argomento preferito all'esame perché combina due specifiche contemporaneamente: algoritmi di ordinamento e complessità.

Algoritmo	Caso migliore	Caso peggiore
Bubble sort	O(n)	O(n²)
Insertion sort	O(n)	O(n²)
Merge sort	O(n log n)	O(n log n)
Binary search	O(1)	O(log n)
Linear search	O(1)	O(n)

La coerenza di merge sort (stessa complessità nel caso migliore e peggiore) vale la pena menzionare esplicitamente se una domanda chiede perché lo sceglieresti rispetto a bubble sort per dataset grandi. Il caso migliore O(n) di bubble sort si applica solo con un'ottimizzazione di uscita anticipata quando non accadono scambi in un passaggio — menziona quel dettaglio se lo porti in tavolo, poiché alcuni enti esaminatori lo richiedono.

Dove gli studenti perdono punti

Il più grande: scrivere