Vad kursen täckte och vad den hoppade över
Hammings kurs täckte: analog-till-digital-omvandling, felrättande koder, simulering, statistik, numerisk analys och n-dimensionell geometri. Han tänkte beräkningsmässigt — signalbehandling, kodningsteori och digital filtrering kräver alla beräkningsmässigt resonemang.
Han undervisade aldrig systematiskt om algoritmisk komplexitet.
Varför luckan uppstod
Hammings mentala modell formades under en tid då hårdvarubegränsningar dominerade. Frågan var: hur många transistorer per chip? Algoritmen kördes på den tillgängliga hårdvaran. Vid N=100 kostar en O(N²)-algoritm 10 000 operationer. Vid N=1 000 kostar den 1 000 000. Vid N=10 000 (vanligt idag i beroendegrafer, sociala nätverk och pakethanterare) kostar den 100 000 000. Skillnaden mellan O(N) och O(N²) var osynlig i de skalor Hamming arbetade med och katastrofal i de skalor hans studenter skulle möta.
Donald Knuth publicerade The Art of Computer Programming från och med 1968 — samma år som Hamming var som mest produktiv i sin forskning. Big O-notation blev standardvokabulär inom algoritmer under 1970- och 1980-talen. Hammings kurs är från 1995, men hans mentala modell av beräkning formades tidigare. Han uppdaterade aldrig detta kapitel.
Ett fundament enligt Hammings eget test
Hammings test för ett fundament: (1) det har bestått länge, (2) resten av fältet kan härledas från det med standardmetoder.
Big O klarar båda testen. Analys av tillväxthastighet har bestått sedan Knuth. Från den härleder du algoritmval, datastrukturval och prestandaprognoser — det mesta av praktisk datavetenskap följer av att fråga ”hur växer kostnaden när N växer?” Hamming missade det mest bestående fundamentet i sitt eget fält.
Big O som ett fundament
Hamming lärde ut att fundament överlever specifika teknologier. Han använde kalkyl som exempel: uppfunnen en gång, tillämpbar inom fysik, teknik, ekonomi och biologi i århundraden. Perifera verktyg kommer och går; fundament ackumuleras.
Hur kostnaden växer
Big O mäter hur kostnaden växer när indata växer. Inte konstantfaktorn — hastigheten. Två algoritmer som båda körs på ”några millisekunder” vid N=100 kan skilja sig med en faktor 10 000 vid N=10 000, om den ena körs i O(N)-tid och den andra i O(N²)-tid.
De vanliga komplexitetsklasserna
O(1) — Konstant. Samma kostnad oavsett N. Exempel: hash-tabelluppslagning med nyckel, arrayåtkomst med index, stack push/pop. Att dubbla N ändrar ingenting.
O(log N) — Logaritmisk. Varje steg halverar det återstående arbetet. Exempel: binärsökning i en sorterad array, BVH-spatialfråga i en spelmotor, operationer på balanserade binära träd. Vid N=1 000 000: log₂(1 000 000) ≈ 20 steg.
O(N) — Linjär. Kostnaden växer med indata. Exempel: linjär genomgång av en lista, läsning av en fil, räkning av objekt i en samling. Vid N=10 000: 10 000 operationer.
O(N log N) — Linjärlogaritmisk. Nästan linjär, något sämre. Exempel: mergesort, effektiva kortaste-väg-algoritmer (Dijkstra med heap). Vid N=10 000: ~133 000 operationer.
O(N²) — Kvadratisk. Kostnaden exploderar. Exempel: list.contains() anropad inuti en loop över samma lista, bubblesort, naiv jämförelse av alla par. Vid N=1 000: 1 000 000 operationer. Vid N=10 000: 100 000 000 operationer.
O(2^N) — Exponentiell. Oanvändbar i någon meningsfull skala. Exempel: brute-force kombinatorik, hitta alla delmängder. Vid N=30: över 1 000 000 000 operationer.
Skalan som gör det synligt
N=10 jämförelser:
O(N): 10
O(N²): 100
ratio: 10x
N=1 000 jämförelser:
O(N): 1 000
O(N²): 1 000 000
ratio: 1 000x
N=10 000 jämförelser:
O(N): 10,000
O(N²): 100,000,000
ratio: 10,000xVid N=10 är skillnaden knappt märkbar. Vid N=10 000 körs O(N²)-algoritmen 10 000 gånger långsammare. Det är därför MOAD-0001 förblev osynlig i årtionden: graferna den kördes på 1993 hade 50 noder. År 2020 kördes samma kod på beroendegrafer med 50 000 noder.
Klassificera tre operationer
Tillämpa komplexitetsklasserna på konkreta operationer. Nyckelfrågan för varje: hur många operationer tar det när N växer?
Korrekt kod, fel tillväxtkurva
Korrekt kod som körs i O(N²)-tid ger identiska resultat som O(N)-kod. Testerna passerar. Utdata matchar. Inget undantag utlöses. Felet döljer sig i tillväxtkurvan.
Denna egenskap gör O(N²)-fel sedimentära: de förstenas inuti fungerande kod och blir synliga först när N växer förbi en tröskel. Koden ändrades inte. Världen omkring den gjorde det.
MOAD-0001: Det sedimentära felet
Det mest förekommande exemplet: visited = [] inuti en loop för grafgenomgång.
visited = []
for node in graph:
if node not in visited: # O(N)-genomsökning vid varje anrop
visited.append(node)
process(node)Varje not in visited-anrop skannar 0 till len(visited)-1 element. N anrop × N/2 genomsnittligt antal skannade element = O(N²) totalt. Fixen: en rad.
visited = set() # O(1) medlemskapstest
for node in graph:
if node not in visited: # O(1) hash-uppslag
visited.add(node)
process(node)Samma beteende. Samma utdata. Samma tester som klarar sig. Tillväxttakten ändras från O(N²) till O(N). Vid N=1 000: 1 000× snabbare. Vid N=10 000: 10 000× snabbare.
Varför Hammings era sådde detta
I tidig Java & C var ArrayList (dynamisk array) den vanliga sekventiella behållaren. Mängder (sets) fanns men var inte idiomatiska — utvecklare valde det de kände till. En grafgenomgång 1993 med N=50 kördes på mikrosekunder med visited = []. Koden hamnade i versionshantering, kopierades, paketerades i bibliotek och distribuerades via pakethanterare. År 2020 kördes samma mönster på beroendegrafar med 50 000 noder.
Koden var korrekt 1993. Den blev dyr när världen runt den förändrades. Hammings era sådde denna typ av defekt genom att aldrig ställa tillväxttaksfrågan.
Diagnostisera & åtgärda
Tillämpa diagnosen: hitta O(N²)-mönstret, identifiera åtgärden.
Vilka namnändringar
Innan Big O hade ett namn märkte programmerare att "detta körs långsamt". De profilerade. De skrev om. Men de kunde inte lära ut mönstret — de kunde bara peka på enskilda fall. Ett mönster utan namn kan inte spridas.
När Big O hade fått ett namn kunde en senior utvecklare säga "detta är O(N²), ersätt det med en mängd" och en junior utvecklare kunde förstå, tillämpa och i sin tur lära ut mönstret. Namnet gjorde mönstret till en överförbar kunskapsenhet.
Hamming kände till detta dynamik i andra områden. Han beskrev hur namngivningen av "spaghettikod" på 1960-talet gjorde det möjligt för gemenskapen att känna igen, diskutera och slutligen utrota en klass av fel som alla hade upplevt men ingen hade namngivit. Samma mekanism gäller för komplexitetsklasser.
Unhamming lägger till det vokabulär som Hamming utelämnade: O(1), O(log N), O(N), O(N log N), O(N²), O(2^N). Dessa namn låter dig se tillväxtkurvan i kod du läser, förutsäga prestanda vid skalning och kommunicera fixar precist. De uppfyller Hammings eget test för en fundamental: varaktig och generativ för det mesta av resten av fältet. [TITLE who_coined_big_o/]
Från talteori till datavetenskap
Big O-notationen har inte sitt ursprung i datavetenskap. Den uppstod inom ren matematik — närmare bestämt inom talteori — 74 år innan Donald Knuth anpassade den för algoritmer.
Paul Bachmann, 1894
Paul Bachmann, en tysk matematiker, introducerade O-notationen i sin bok från 1894 Die Analytische Zahlentheorie (Analytisk talteori). Han behövde ett kompakt sätt att uttrycka att en kvantitet inte växer snabbare än en annan, upp till en konstant faktor. Att skriva 'f(n) = O(g(n))' betydde: f växer högst lika snabbt som g. Detta gjorde det möjligt för talteoretiker att resonera kring feltermer i approximationer utan att behöva hålla reda på exakta konstanter.
Bachmann tänkte inte på loopar, datastrukturer eller exekveringstid. Han funderade på hur primtal fördelar sig — särskilt på feltermerna i primtalssatsen.
Edmund Landau, 1909
Edmund Landau, en annan tysk matematiker, populariserade notationen i sin bok från 1909 Handbuch der Lehre von der Verteilung der Primzahlen (Handbok om fördelningen av primtal). Landau introducerade även den relaterade notationen o (little-o) och använde familjen av asymptotiska symboler så flitigt att den kom att kallas Bachmann-Landau-notation eller helt enkelt Landau-notation.
Under sex decennier levde O-notationen helt inom matematiken. Ingen programmerare tänkte på den.
Donald Knuth, 1968 & 1976
Donald Knuth översatte notationen till datavetenskap. I The Art of Computer Programming (Vol. 1, 1968) använde Knuth O-notation för att beskriva algoritmers körtid — en direkt överföring av Bachmanns verktyg till ett nytt område. Han var den första som systematiskt tillämpade den på algoritmanalys.
1976 publicerade Knuth en kort artikel i SIGACT News med titeln 'Big Omicron and Big Omega and Big Theta.' Han introducerade Omega (Omega) för undre gränser och Theta för snäva gränser, vilket fullbordade det tresymboliga vokabulär som datavetenskap använder idag. Han argumenterade också för att standardisera användningen av dessa symboler inom fältet — en medveten standardiseringsåtgärd som påskyndade adoptionen.
I början av 1980-talet förekom Big O i alla algoritmböcker. På 1990-talet var det standardintervju-vokabulär.
En 74-årig resa
1894 — Bachmann introducerar O inom talteori
1909 — Landau populariserar O, o och hela notationsfamiljen
1953 — Hamming börjar forskning på Bell Labs (lär sig aldrig Big O som CS-verktyg)
1968 — Knuth använder O för algoritmanalys i TAOCP Vol. 1
1976 — Knuth lägger till Omega och Theta; argumenterar för standardisering
1980-talet — Big O kommer in i alla CS-läroplaner
1993 — MOAD-0001 sedimentlager bildas i produktionskod
1995 — Hamming undervisar sista versionen av sin kurs; täcker aldrig Big O
2026 — MOAD-0001 hittas i 1 000+ open-source-projektBachmanns verktyg tillbringade 74 år inom ren matematik, synligt för varje matematiker men osynligt för varje programmerare. Knuth såg transplantationen. Hamming — som arbetade under samma era och samarbetade med samma datormiljö — införde det aldrig i sin undervisning.
Varför Knuths standardisering spelade roll
Knuths artikel från 1976 gjorde mer än att introducera Omega och Theta. Den argumenterade för att området behövde konsekvent notation, och att inkonsekvent notation var direkt skadlig. Olika läroböcker använde O för att betyda olika saker — ibland som en övre gräns, ibland som en approximation, ibland utan att ange om konstanter spelade roll. Knuth rensade upp detta.
Detta är Hammings mönster-namngivningsdynamik tillämpad på notationen själv. Innan Knuth standardiserade symbolerna kunde ingenjörer inte kommunicera komplexitetsanspråk exakt mellan läroböcker, artiklar eller team. Efter standardiseringen bar "this runs in O(N log N)" exakt en betydelse oavsett vem som sa det.
Knuth bidrog också med den informella översättningen: "O(f(n)) betyder att körtiden är högst en konstant gånger f(n), för alla tillräckligt stora n." Denna tolkning — övre gräns, upp till en konstant faktor, för stora indata — blev den standardintuition varje programmerare lär sig.