Ce înseamnă notația Big O și de ce spunem că 3n + 5 și n au aceeași complexitate?
Răspuns scurt: Big O descrie cum crește timpul (sau memoria) unui algoritm când crește dimensiunea intrării n, ca limită superioară. Constantele și termenii mai mici se ignoră, pentru că nu schimbă forma creșterii pentru n mare.
Big O nu măsoară secunde, ci rata de creștere. Întrebarea la care răspunde este: dacă dublez intrarea, cât de mult crește munca? Pentru 3n + 5, dublarea lui n aproape dublează numărul de operații, exact ca pentru n. De aceea ambele sunt O(n).
Regulile practice:
- ignori constantele multiplicative: O(3n) devine O(n), O(n/2) devine O(n);
- păstrezi doar termenul dominant: O(n² + n log n + 100) devine O(n²);
- intrări diferite au variabile diferite: două bucle succesive pe liste diferite sunt O(n + m), nu O(n).
De ce ignorăm constantele? Pentru că depind de limbaj, de procesor și de implementare, pe când forma creșterii nu depinde. Un algoritm O(n log n) scris lent va bate, de la un n suficient de mare, un algoritm O(n²) scris foarte eficient.
Constantele contează totuși în practică pentru n mic: o sortare prin inserție poate fi mai rapidă decât merge sort pe 20 de elemente, motiv pentru care Timsort, sortarea din Python, folosește inserția pe bucăți mici. La interviu spui complexitatea în Big O, iar dacă ai două soluții cu aceeași complexitate, poți discuta și constantele.
Ordinea uzuală, de la rapid la lent: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!).
Ce urmărește intervievatorul: Verifică dacă înțelegi ce măsoară Big O, nu doar dacă recunoști notația. Greșeala tipică este să spui „O(2n)” sau să aduni complexitățile a două intrări diferite într-un singur n.
