Big O Notation للمبتدئ: ليه نفس الكود بياخد ثانيتين أو 4 ساعات

كود يوضّح الفرق بين O(n²) و O(n)

المشكلة: عندك array فيه أرقام، وعايز تلاقي أول رقمين مجموعهم 100.

على Node.js 22 و array فيه مليون رقم عشوائي (متوسط 10 تشغيلات):

• findPairNaive: 4.8 ثانية.
• findPairFast: 38 مللي ثانية.

الفرق 126 ضعف على نفس الـ CPU وبنفس البيانات. السبب الرياضي: الـ O(n²) بتعمل تقريبًا 5×10¹¹ مقارنة (n×(n-1)/2)، والـ O(n) بتعمل مليون عملية فقط.

إزاي تحسب Big O لكودك في 30 ثانية

1. عُد عدد الـ loops اللي بيمشوا على البيانات. loop واحدة على n عنصر → O(n). loop داخل loop على نفس البيانات → O(n²).
2. أي عملية ثابتة (وصول لـ object property، مقارنة، إسناد، عملية حسابية) = O(1)، تجاهلها.
3. أي recursive call بيقسم البيانات نصف → ضيف log n. مثال: binary search، merge sort.
4. المجموع: تجاهل الثوابت والـ lower-order terms. 3n² + 100n + 5 = O(n²).

متى Big O بتخدعك (trade-offs حقيقية)

Big O بتقيس النمو، مش الزمن المطلق. algorithm O(n) ممكن يكون أبطأ من O(n²) على بيانات صغيرة، لأن O(n²) تكلفته الثابتة أقل (مفيش allocation لـ Set، مفيش hashing). مثال موثّق: insertion sort O(n²) أسرع من merge sort O(n log n) لو الـ array أصغر من 16 عنصر. علشان كده V8 و GCC و OpenJDK كلهم بيستخدموا hybrid sorting (Timsort، Introsort) يبدأ بـ quicksort أو merge sort ويبدّل لـ insertion sort لو الجزء صغير.

الـ trade-off التاني: O(n) دايمًا بياكل ذاكرة أكثر. الـ findPairFast فوق بيستخدم Set بـ O(n) من الذاكرة. لو البيانات 100GB ومش متسعة في الـ RAM، الـ O(n²) ممكن يكون الاختيار الأفضل لأنه in-place. الافتراض هنا: انت شغّال على بيانات أصغر من ذاكرة الـ process المتاحة.

متى لا تستخدم Big O أصلًا

لو البيانات اللي بتشتغل عليها أقل من 1,000 عنصر دايمًا، الفرق بين O(n) و O(n²) ميكروثوانٍ. اهتم بقراءة الكود وسهولة الصيانة بدل ما تـ premature optimize. القاعدة من Donald Knuth نفسه: "Premature optimization is the root of all evil" (Computing Surveys، ديسمبر 1974). Big O بتبقى مهمة في حالتين بس:

• لما البيانات بتعدّي 10,000 عنصر باستمرار.
• لما الكود بيتنفّذ ملايين المرات (hot path: request handler، loop داخلي).

الخطوة التالية

افتح أبطأ function في الكود بتاعك. عُد الـ loops. لو لقيت loop داخل loop على نفس البيانات، استبدلها بـ Map أو Set وقيس الفرق. لو الفرق محسوس (10× وأكتر)، انت كنت في O(n²) فعلًا. لو بتعمل linear search في array مرتّب، استخدم binary search مباشرة — موجودة جاهزة في lodash.sortedIndexOf أو Python bisect.

المصادر

• Donald Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, Addison-Wesley, 1968 — التعريف الأصلي لـ Big O Notation في علوم الحاسب.
• Donald Knuth, "Structured Programming with go to Statements", ACM Computing Surveys, Vol. 6, No. 4, ديسمبر 1974 — مصدر مقولة "Premature optimization".
• Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein, Introduction to Algorithms (CLRS), 4th edition, MIT Press, 2022 — الفصل 3 يشرح Asymptotic Notation بالكامل.
• V8 Engine Source Code, Timsort implementation: v8/third_party/v8/builtins/array-sort.tq.
• Tim Peters, "Timsort description", Python source Objects/listsort.txt — أصل الـ hybrid sorting المستخدم في Python و JavaScript.