Big O Notation Nedir? Algoritma Karmaşıklığını Gerçek Örneklerle Anlamak

10 elemanlı bir dizide mükemmel çalışan bir fonksiyon yazıyorsunuz. Test geçiyor, code review onaylanıyor, production'a gidiyor. Üç ay sonra veri 10 milyona ulaştığında sistem yanıt vermez oluyor.

Bu senaryo gerçek. Ve Big O'yu anlamayan geliştiricilerin başına defalarca gelir.

Big O Notation Nedir?

Big O Notation, bir algoritmanın girdi boyutu büyüdükçe nasıl davranacağını — zaman ve bellek açısından — tanımlamak için kullanılan matematiksel gösterimdir. Algoritmanın en kötü durumda ne kadar kaynak tüketeceğini söyler.

Önemli olan: mutlak süre değil, büyüme hızı. Bir fonksiyonun 10ms mi yoksa 20ms mi çalıştığı ortama göre değişir. Ama veri iki katına çıktığında süre de iki katına mı çıkıyor, dört katına mı, yoksa logaritmik mi artıyor — bu evrenseldir.

O(1) — Sabit Zaman

Girdi ne kadar büyük olursa olsun, işlem aynı sürede tamamlanır.

// Dizinin ilk elemanına erişim - her zaman O(1)
function getFirst(arr) {
  return arr[0];
}

// Object'ten değer okuma - her zaman O(1)
function getUser(users, id) {
  return users[id]; // hash map lookup
}

getFirst([1]);                        // 1ms
getFirst([1, 2, 3, ..., 10000000]);   // 1ms (aynı)

Array index erişimi, hash map okuma, stack push/pop — bunlar O(1)'dir. Veri ne kadar büyürse büyüsün, süre değişmez.

O(log n) — Logaritmik Zaman

Her adımda problem yarıya iner. Veri iki katına çıktığında sadece bir adım eklenir.

// Binary Search - sıralı dizide eleman arama
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

1.000 elemanlı dizide maksimum 10 adım. 1.000.000 elemanlı dizide maksimum 20 adım. 1.000.000.000'da 30 adım. Veri milyar katına çıksa da sadece 30 adım eklendi.

Binary search, balanced binary tree araması, heap işlemleri — O(log n)'dir.

O(n) — Lineer Zaman

Her eleman bir kez işlenir. Veri iki katına çıkınca süre de iki katına çıkar.

// Dizide eleman arama - en kötü durumda her elemana bakılır
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

// Toplam hesaplama
function sum(arr) {
  return arr.reduce((total, num) => total + num, 0);
}

1.000 elemanlı dizide 1.000 adım. 1.000.000'da 1.000.000 adım. Doğrusal büyüme.

O(n log n) — Lineer Logaritmik Zaman

Çoğu verimli sıralama algoritması buradadır. O(n)'den kötü ama O(n²)'den çok daha iyi.

// Merge Sort - O(n log n)
function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }

  return [...result, ...left.slice(i), ...right.slice(j)];
}

JavaScript'in Array.sort(), Python'un sorted() — hepsi O(n log n)'dir.

O(n²) — Karesel Zaman

İç içe iki döngü. Veri iki katına çıkınca süre dört katına çıkar.

// Bubble Sort - O(n²)
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

// Klasik hata: iç içe döngüyle duplicate bulma
function hasDuplicates(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return true; // O(n²)
    }
  }
  return false;
}

// Doğru yaklaşım: Set kullanarak O(n)
function hasDuplicatesFast(arr) {
  return new Set(arr).size !== arr.length; // O(n)
}

1.000 elemanlı dizide 1.000.000 işlem. 10.000'de 100.000.000 işlem. Bu neden production'da sistem çökertir.

O(2ⁿ) — Üstel Zaman

Her adımda işlem sayısı iki katına çıkar. Küçük girdilerle bile hızla kullanılamaz hale gelir.

// Fibonacci - naif recursive (O(2^n))
function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2); // her çağrı iki dal oluşturur
}

fibonacci(10)  // 177 çağrı
fibonacci(20)  // 21.891 çağrı
fibonacci(40)  // 331.160.281 çağrı
fibonacci(50)  // trilyonlarca çağrı → sistem donar

Memoization ile O(n)'e düşürülür:

// Fibonacci - memoization ile O(n)
function fibonacci(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}

Karşılaştırma: Sayılarla Görmek

n değeri büyüdükçe fark ne kadar dramatik:

n = 10:
  O(1)      → 1 işlem
  O(log n)  → 3 işlem
  O(n)      → 10 işlem
  O(n log n)→ 33 işlem
  O(n²)     → 100 işlem

n = 1.000:
  O(1)      → 1 işlem
  O(log n)  → 10 işlem
  O(n)      → 1.000 işlem
  O(n log n)→ 10.000 işlem
  O(n²)     → 1.000.000 işlem

n = 1.000.000:
  O(1)      → 1 işlem
  O(log n)  → 20 işlem
  O(n)      → 1.000.000 işlem
  O(n log n)→ 20.000.000 işlem
  O(n²)     → 1.000.000.000.000 işlem  ← artık dakikalar/saatler

Space Complexity: Zaman Değil Bellek

Big O sadece zaman için değil, bellek kullanımı için de geçerlidir.

// O(1) space - sabit bellek kullanımı
function sum(arr) {
  let total = 0; // tek bir değişken
  for (const num of arr) total += num;
  return total;
}

// O(n) space - girdi kadar bellek
function double(arr) {
  return arr.map(x => x * 2); // yeni dizi oluşturur
}

// Recursive fonksiyonlar call stack'te yer tutar
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1); // O(n) space — n derinliğinde stack
}

Pratik Kural: Ne Zaman Önemli?

Her kod parçasının Big O'sunu hesaplamak gerekmez. Önemli olduğu durumlar: büyük veri setleri üzerinde çalışan fonksiyonlar, döngü içinde çağrılan fonksiyonlar, veritabanı sorguları (N+1 problemi), API endpoint'lerinin yanıt süresi.

Küçük sabit boyutlu veri için O(n²) kabul edilebilir. Büyüyen veri için O(n log n) veya daha iyi hedefleyin.

Kod yazarken sorun: "Bu 1000 kat daha büyük veriyle nasıl davranır?" Cevabı bilmek, production surprize karşı en iyi sigortanızdır.