Big-O beschrijft hoe de rekentijd of geheugengebruik van een algoritme groeit naarmate de invoergrootte n groeit. Het beschrijft het worst-case asymptotische gedrag, waarbij constanten en termen van lager orde worden genegeerd.
We geven om de groeisnelheid, niet om exacte stappenaantallen. O(2n + 5) is gewoon O(n) omdat constanten en kleinere termen niet meer uitmaken naarmate n groot wordt.
| Big-O | Naam | Voorbeeld |
|---|
| O(1) | constant | array index lookup |
| O(log n) | logaritmisch | binary search |
| O(n) | lineair | een lijst scannen |
| O(n log n) | linearitmisch | merge sort |
| O(n²) | kwadratisch | geneste lussen |
| O(2ⁿ) | exponentieel | naive subsets |
def has_duplicate(nums):
for i in range(len(nums)): # outer loop: n
for j in range(i + 1, len(nums)): # inner loop: n
if nums[i] == nums[j]:
return True
return False
# nested loops -> O(n^2) time, O(1) space
Big-O verbergt constanten: een O(n) algoritme met een grote constante kan verliezen van O(n log n) op kleine invoeren. Volg ook de space complexiteit, niet alleen time.
Big-O laat je algoritmen vergelijken zonder ze uit te voeren of je zorgen te maken over hardware.
Het voorspelt welke oplossingen standhouden wanneer invoeren groeien van honderden tot miljoenen — het verschil tussen een feature die schaalt en een die timeout geeft.
Het is het vocabulaire dat elke engineer gebruikt om over performance te redeneren.