Big O Notation: Ce se asteapta intr-adevar A-Level CS

Notația Big O apare pe fiecare spec major de informatică A-level (AQA, OCR, Edexcel) și încurcă mulți studenți nu pentru că matematica e grea, ci pentru că nu o văd legată de codul real. Aceasta este o prezentare practică a ceea ce trebuie să știi și cum să răspunzi la întrebări de examen pe acest subiect fără să te complici.

Ce măsoară de fapt Big O

Big O descrie modul în care timpul de execuție (sau memoria folosită) a unui algoritm crește pe măsură ce dimensiunea intrării, numită de obicei n, devine mai mare. Nu e o măsurare cu cronometrul în secunde. E o modalitate de a descrie rata de creștere pentru a putea compara algoritmi independent de hardware.

Când scrii O(n), spui: dacă dublez intrarea, munca se dublează aproximativ. O(n²) înseamnă că dublând intrarea munca se cvadruplează aproximativ. Acea relație e ceea ce examinatorii vor să identifici, nu numărătorile exacte de operații.

Complexitățile pe care trebuie să le cunosti bine

Pentru A-level, acestea sunt cele care apar din nou și din nou:

• O(1) – timp constant. Accesarea unui element de matrice după index: arr[5]. Nu conteaza cât de mare e matricea.
• O(log n) – logaritmic. Căutarea binară într-o listă sortată. Fiecare pas înjumătățește spațiul de căutare rămas.
• O(n) – liniar. O buclă simplă prin lista, ca o căutare liniară verificând fiecare element o dată.
• O(n log n) – liniaritmic. Merge sort și quicksort (caz mediu) se găsesc aici.
• O(n²) – pătratic. Bucle imbricate peste aceleași date, exact ceea ce fac bubble sort, insertion sort și selection sort.
• O(2ⁿ) – exponențial. Fibonacci recursiv naiv fără memoizare. Devine dezastru repede.

Trebuie să poți privi pseudocodul și să spui care dintre acestea e pe loc, pentru că aia e în principal ceea ce se testează.

Citirea codului pentru complexitate

Metoda care funcționează de fiecare dată: numără buclele și vezi cum se raportează la n.

# O(n) - o buclă, o trecere
for i in range(n):
    print(i)

# O(n^2) - buclă imbricată, ambele legate de n
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - spațiul de căutare se înjumătățește la fiecare iterație
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

O buclă imbricată în care intervalul buclei interioare depinde de n e tot O(n²), chiar dacă arată ușor diferit (cum ar fi for j in range(i) în loc de for j in range(n) — aia e tot pătratic în general, doar cu o diferență de factor constant).

Fii atent la buclele care nu depind deloc de n. O buclă care rulează întotdeauna de 10 ori indiferent de dimensiunea intrării e O(1), chiar dacă e o buclă prezentă. Examinatorii iubesc să ascundă asta.

Algoritmi comuni de sortare și Big O

Aceasta e un subiect favorit de examen pentru că combină două spec-uri deodată: algoritmi de sortare și complexitate.

Algoritm	Caz optim	Caz pesim
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)

Consecvența merge sort-ului (aceeași complexitate caz optim și pesim) merită menționată explicit dacă o întrebare îți cere de ce l-ai alege peste bubble sort pentru dataset-uri mari. Cazul optim al bubble sort-ului de O(n) se aplică doar cu o optimizare de ieșire timpurie când nu se întâmplă swapuri într-o trecere — menționează detaliul ala dacă o aduci în discuție, pentru că unele boarduri de examen se așteptă la asta.

Unde pierd studenții puncte

Celul mai mare: scriere