מיליון איברים. שתי פונקציות. אחת מסיימת ב-20 מיליסקונד, השנייה לוקחת 20 דקות. לא בגלל שמישהו כתב קוד גרוע - בגלל שמישהו בחר אלגוריתם בלי להבין את ה-Complexity שלו.
ההפרש בין O(n) ל-O(n²) על מיליון איברים
20ms מול 20 דקות. אותו hardware. אותו קוד שכמעט עובד.
Big-O Notation הוא השפה שבה Senior Engineers מדברים על ביצועים. כשמהנדס ב-Google אומר שהפתרון הוא O(n log n), הוא לא מספר לכם כמה שניות זה לוקח - הוא מספר איך הזמן גדל כשהקלט גדל. זה הבסיס לכל ניתוח אלגוריתמי שתעשו בראיונות וב-Production.