Come Cresce il Costo

Big O misura come il costo cresce al crescere dell'input. Non il fattore costante — il tasso. Due algoritmi che entrambi eseguono in 'pochi millisecondi' a N=100 possono divergere di un fattore di 10.000 a N=10.000, se uno esegue in tempo O(N) e l'altro in O(N²).

Le Classi di Complessità Comuni

O(1) — Costante. Stesso costo indipendentemente da N. Esempi: ricerca in tabella hash per chiave, accesso a un array per indice, push/pop su stack. Raddoppiare N non cambia nulla.

O(log N) — Logaritmico. Ogni passo dimezza il lavoro rimanente. Esempi: ricerca binaria in un array ordinato, query spaziale BVH in un motore di gioco, operazioni su alberi binari bilanciati. Con N=1.000.000: log₂(1.000.000) ≈ 20 passi.

O(N) — Lineare. Il costo cresce con l'input. Esempi: scansione lineare di una lista, lettura di un file, conteggio degli elementi in una collezione. Con N=10.000: 10.000 operazioni.

O(N log N) — Linearitmico. Quasi lineare, leggermente peggiore. Esempi: merge sort, algoritmi efficienti per il percorso più breve (Dijkstra con heap). Con N=10.000: ~133.000 operazioni.

O(N²) — Quadratico. Il costo esplode. Esempi: list.contains() chiamato all'interno di un ciclo sulla stessa lista, bubble sort, confronto ingenuo di tutte le coppie. Con N=1.000: 1.000.000 operazioni. Con N=10.000: 100.000.000 operazioni.

O(2^N) — Esponenziale. Inutilizzabile a qualsiasi scala significativa. Esempi: combinatoria brute-force, ricerca di tutti i sottoinsiemi. Con N=30: oltre 1.000.000.000 operazioni.

La scala che lo rende visibile

N=10 confronti:
O(N):   10
O(N²):  100
ratio:  10x

N=1.000 confronti:
O(N):   1.000
O(N²):  1.000.000
ratio:  1.000x

N=10.000 confronti:
O(N):   10.000
O(N²):  100.000.000
ratio:  10.000x

A N=10, la differenza è appena percepibile. A N=10.000, l’algoritmo O(N²) è 10.000 volte più lento. Ecco perché MOAD-0001 è rimasto invisibile per decenni: i grafi su cui veniva eseguito nel 1993 avevano 50 nodi. Nel 2020, lo stesso codice veniva eseguito su grafi di dipendenze con 50.000 nodi.

Classifica tre operazioni

Applica le classi di complessità a operazioni concrete. La domanda chiave per ciascuna: quante operazioni richiede al crescere di N?

Codice Corretto, Curva di Crescita Errata

Codice corretto che esegue in tempo O(N²) produce risultati identici al codice O(N). I test passano. L'output corrisponde. Nessuna eccezione viene sollevata. Il difetto si nasconde nella curva di crescita.

Questa proprietà rende i difetti O(N²) sedimentari: si calcificano all'interno di codice funzionante e diventano visibili solo quando N supera una certa soglia. Il codice non è cambiato. È il mondo intorno a esso che è cambiato.

MOAD-0001: Il Difetto Sedimentario

L'istanza più diffusa: visited = [] all'interno di un ciclo di attraversamento di un grafo.

visited = []
for node in graph:
if node not in visited:  # scansione O(N) a ogni chiamata
visited.append(node)
process(node)

Ogni chiamata not in visited esamina da 0 a len(visited)-1 elementi. N chiamate × N/2 elementi mediamente esaminati = O(N²) totale. La soluzione: una sola riga.

visited = set()  # test di appartenenza O(1)
for node in graph:
if node not in visited:  # lookup hash O(1)
visited.add(node)
process(node)

Stesso comportamento. Stesso output. Stessi test superati. Il tasso di crescita passa da O(N²) a O(N). A N=1.000: 1.000× più veloce. A N=10.000: 10.000× più veloce.

Perché l'era di Hamming ha generato questo problema

Nei primi Java e C, ArrayList (array dinamico) era il contenitore sequenziale predefinito. I set esistevano ma non erano idiomatici: gli sviluppatori usavano ciò che conoscevano. Un attraversamento di grafo del 1993 con N=50 veniva eseguito in microsecondi con visited = []. Quel codice entrò nel version control, fu copiato, incapsulato in librerie e distribuito tramite package manager. Nel 2020 lo stesso pattern girava su grafi di dipendenze con 50.000 nodi.

Il codice era corretto nel 1993. Diventò costoso quando il mondo intorno cambiò. L'era di Hamming ha generato questa classe di difetti non ponendo mai la domanda sul tasso di crescita.

Diagnosi e correzione

Applica la diagnosi: individua il pattern O(N²) e identifica la correzione.

Quali modifiche ai nomi

Prima che Big O avesse un nome, i programmatori notavano "questo è lento". Facevano profiling. Riscrivevano. Ma non potevano insegnare lo schema — potevano solo indicare casi singoli. Uno schema senza nome non può propagarsi.

Dopo che Big O ebbe un nome, un ingegnere senior poteva dire "questo è O(N²), sostituiscilo con un set" e un ingegnere junior poteva capire, applicare e a sua volta insegnare lo schema. Il nome ha reso lo schema un'unità di conoscenza trasferibile.

Hamming conosceva questa dinamica in altri ambiti. Descrisse come nominare "spaghetti code" negli anni '60 permise alla comunità di riconoscere, discutere ed eventualmente eliminare una classe di difetti che tutti avevano sperimentato ma nessuno aveva nominato. Lo stesso meccanismo si applica alle classi di complessità.

Unhamming aggiunge il vocabolario che Hamming omise: O(1), O(log N), O(N), O(N log N), O(N²), O(2^N). Questi nomi ti permettono di vedere la curva di crescita nel codice che leggi, prevedere le prestazioni su larga scala e comunicare le correzioni in modo preciso. Soddisfano il criterio stesso di Hamming per un concetto fondamentale: duraturo e generativo della maggior parte del resto del campo. [TITLE who_coined_big_o/]

Dalla Teoria dei Numeri all’Informatica

La notazione Big O non ha avuto origine nell’informatica. È nata nella matematica pura — in particolare nella teoria dei numeri — 74 anni prima che Donald Knuth la adattasse agli algoritmi.

Paul Bachmann, 1894

Paul Bachmann, matematico tedesco, introdusse la notazione O nel suo libro del 1894 Die Analytische Zahlentheorie (Teoria Analitica dei Numeri). Aveva bisogno di un modo compatto per esprimere che una quantità cresce non più velocemente di un’altra, a meno di un fattore costante. Scrivere “f(n) = O(g(n))” significava: f cresce al massimo quanto g. Questo permise ai teorici dei numeri di ragionare sui termini di errore nelle approssimazioni senza dover tenere traccia delle costanti esatte.

Bachmann non stava pensando a cicli, strutture dati o tempi di esecuzione. Stava pensando a come si distribuiscono i numeri primi — in particolare ai termini di errore nel Teorema dei Numeri Primi.

Edmund Landau, 1909

Edmund Landau, un altro matematico tedesco, rese popolare la notazione nel suo Handbuch der Lehre von der Verteilung der Primzahlen (Manuale sulla Distribuzione dei Numeri Primi) del 1909. Landau introdusse anche la notazione correlata o (little-o) e usò così estesamente la famiglia dei simboli asintotici che questa divenne nota come notazione di Bachmann-Landau o semplicemente notazione di Landau.

Per sei decenni, la notazione O visse esclusivamente in ambito matematico. Nessun programmatore ci pensava.

Donald Knuth, 1968 & 1976

Donald Knuth ha tradotto la notazione nel campo dell'informatica. In The Art of Computer Programming (Vol. 1, 1968), Knuth ha usato la notazione O per descrivere il tempo di esecuzione degli algoritmi — un trasferimento diretto dello strumento di Bachmann in un nuovo dominio. È stato il primo a applicarla sistematicamente all'analisi degli algoritmi.

Nel 1976, Knuth pubblicò un breve articolo su SIGACT News intitolato 'Big Omicron and Big Omega and Big Theta.' Introdusse Omega (Omega) per i limiti inferiori e Theta per i limiti stretti, completando il vocabolario a tre simboli che l'informatica utilizza oggi. Argomentò inoltre a favore della standardizzazione dell'uso di questi simboli nel campo — un atto di standardizzazione deliberata che accelerò l'adozione.

All'inizio degli anni '80, la notazione Big O apparve in ogni libro di testo sugli algoritmi. Negli anni '90, divenne il vocabolario standard nei colloqui.

Un viaggio di 74 anni

1894 — Bachmann introduce O nella teoria dei numeri
1909 — Landau rende popolare O, o e l'intera famiglia di notazioni
1953 — Hamming inizia la ricerca ai Bell Labs (non impara mai Big O come strumento CS)
1968 — Knuth applica O all'analisi degli algoritmi in TAOCP Vol. 1
1976 — Knuth aggiunge Omega e Theta; sostiene la standardizzazione
1980s — Big O entra in tutti i curricula di CS
1993 — Lo strato sedimentario MOAD-0001 si forma nel codice di produzione
1995 — Hamming insegna l'ultima versione del suo corso; non tratta mai Big O
2026 — MOAD-0001 trovato in oltre 1.000 progetti open-source

Lo strumento di Bachmann rimase per 74 anni nella matematica pura, visibile a ogni matematico ma invisibile a ogni programmatore. Knuth ne vide il trapianto. Hamming — lavorando nella stessa epoca, collaborando con la stessa comunità di informatici — non lo inserì mai nel suo corso.

Perché la standardizzazione di Knuth fu importante

L’articolo di Knuth del 1976 fece qualcosa di più che introdurre Omega e Theta. Sostenne che il campo necessitava di una notazione coerente e che una notazione incoerente era attivamente dannosa. Diversi libri di testo usavano O per indicare cose diverse — a volte un limite superiore, a volte un’approssimazione, a volte senza specificare se le costanti contassero. Knuth mise ordine.

È la dinamica di denominazione dei pattern di Hamming applicata alla notazione stessa. Prima che Knuth standardizzasse i simboli, gli ingegneri non potevano comunicare affermazioni sulla complessità in modo preciso tra libri di testo, articoli o team. Dopo la standardizzazione, “questo algoritmo ha complessità O(N log N)” aveva esattamente un solo significato, indipendentemente da chi lo dicesse.

Knuth fornì anche la traduzione informale: “O(f(n)) significa che il tempo di esecuzione è al massimo una costante moltiplicata per f(n), per tutti gli n sufficientemente grandi”. Questa interpretazione — limite superiore, fino a un fattore costante, per input grandi — divenne l’intuizione standard che ogni programmatore impara.