WEEK 1 • تحليل الخوارزميات

Big O Notation

ترميز Big O - تحليل التعقيد

The mathematical notation used to describe the performance and efficiency of algorithms as input size grows.

إيه هو Big O؟

What is Big O Notation?

📊 الفكرة الأساسية

🤔 السؤال المهم

لما بتكتب كود، السؤال المهم مش بس "هل الكود بيشتغل؟"
السؤال الأهم: "قد إيه الكود سريع؟ وبيستهلك ذاكرة إزاي؟"

📐 Big O بيقيس إيه؟

Big O Notation هو طريقة رياضية لوصف:

⏱️
Time Complexity

كام عملية (operation) الكود بيعملها؟

💾
Space Complexity

قد إيه ذاكرة الكود بيستهلك؟

🎯 ليه "n"؟

الحرف n بيمثل حجم المدخلات (Input Size).

  • • لو بتدور في array ← n = عدد العناصر
  • • لو بتعالج string ← n = طول الـ string
  • • لو بتتعامل مع matrix ← n × m = الأبعاد

⚡ المهم: الـ Worst Case

Big O بيركز على أسوأ حالة (Worst Case) - يعني لو الحظ وحش، الكود هياخد قد إيه؟

فيه كمان Best Case (أحسن حالة) و Average Case (المتوسط)، بس غالباً بنهتم بالـ Worst.

أنواع التعقيد

Common Complexity Classes - مرتبة من الأسرع للأبطأ

O(1) أسرع ✓

Constant Time

الوقت ثابت - مش مهم حجم الـ input!

📖 تشبيه:

زي إنك تفتح كتاب على صفحة معينة - مش مهم الكتاب فيه كام صفحة.

// Example:
arr[0] // Array access
map.get(key) // Hash lookup
O(log n) سريع جداً

Logarithmic Time

كل ما الـ n يتضاعف، الوقت بيزيد خطوة واحدة بس!

📖 تشبيه:

زي البحث في القاموس - بتقسم النص كل مرة.

n = 1,000,000 → ~20 خطوة
// Example:
binarySearch(arr, target)
O(n) مقبول

Linear Time

الوقت يزيد بنفس نسبة زيادة الـ input.

📖 تشبيه:

زي قراءة كتاب صفحة صفحة - كتاب أكبر = وقت أكتر.

n = 1,000 → ~1,000 عملية
// Example:
for (let i of arr) { ... }
O(n log n) جيد

Linearithmic Time

أحسن ما يمكن لـ خوارزميات الترتيب المبنية على المقارنة.

📖 تشبيه:

زي ترتيب ورق الكوتشينة بطريقة ذكية.

// Examples:
mergeSort(), quickSort()
O(n²) بطيء

Quadratic Time

الوقت بيزيد بمربع حجم الـ input!

⚠️ تحذير:

n = 1000 → مليون عملية!

// Nested loops:
for (i) { for (j) { ... } }

أمثلة: Bubble Sort, Selection Sort

O(2ⁿ) بطيء جداً!

Exponential Time

الوقت بيتضاعف مع كل إضافة للـ input!

⚠️ خطر:

n = 30 → أكتر من مليار عملية!

// Example:
fibonacci(n) // naive

الرسم البياني

Visualize Growth Rates

💡 لاحظ: كل ما n بيزيد، الفرق بين الخوارزميات السريعة والبطيئة بيبقى ضخم جداً!

أمثلة عملية

Real-World Examples

O(1) - Array Index Access 
function getFirst(arr) {
  return arr[0];  // Always ONE operation
}

// Whether arr has 10 or 10,000,000 elements
// This takes the SAME time!

الشرح: الوصول لعنصر في array بالـ index بياخد نفس الوقت سواء الـ array فيها 10 عناصر أو 10 مليون!

السبب: الـ array بتخزن العناصر في ذاكرة متتالية، فالكمبيوتر بيحسب العنوان مباشرة.

O(n) - Linear Search 
function findMax(arr) {
  let max = arr[0];
  
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  
  return max;
}

الشرح: لازم نعدي على كل عنصر عشان نلاقي الأكبر.

لو الـ array فيها n عنصر، هنعمل n مقارنة.
الوقت بيزيد خطياً مع حجم الـ input.

O(n²) - Nested Loops 
function hasDuplicate(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;
      }
    }
  }
  return false;
}

الشرح: Loop جوه loop! كل عنصر بيتقارن بكل العناصر التانية.

n = 100 → ~5,000 مقارنة
n = 1,000 → ~500,000 مقارنة!

💡 ممكن نحسنها لـ O(n) باستخدام Set أو Hash!

Quick Reference

Complexity Name n = 1000 Examples
O(1) Constant 1 Array access, Hash lookup
O(log n) Logarithmic ~10 Binary Search
O(n) Linear 1,000 Linear Search, Single loop
O(n log n) Linearithmic ~10,000 Merge Sort, Quick Sort
O(n²) Quadratic 1,000,000 Bubble Sort, Nested loops
O(2ⁿ) Exponential ∞ Fibonacci (naive), Subsets