היא התחילה לבלבל את השכל על nlogn וכל מיני דברים מוזרים שבחיים לא שמעתי עליהם

היא אפילו לא נתנה הסבר
היא ישר נתנה דוגמא והלכה.

מה זה לעזאזל? איך מחשבים? איך יודעים?

1. סיבוכיות זמן-ריצה, אשר מורה על משך הזמן המוערך לביצוע פעולות שונות. מכיוון שאלגוריתם זהה יבוצע במערכות שונות (כלומר בקומפיילרים שונים, במחשבים שונים ואפילו במערכות-הפעלה וסביבות-עבודה שונות) בזמן שונה, עקב השוני בינהם, הוגדרה יחידת הזמן של הסיבוכיות, כמספר הפעולות שעל המחשב יהיה לבצע בעת הרצת אלגוריתם מסויים.

2. סיבוכיות מקום, אשר מורה על גודל הזיכרון שהאלגוריתם יקצה, ועקב כך, ישאב מן המערכת משאבים.

אני מרשה לעצמי להניח שאתם מעסקים שם עם סיבוכיות זמן-ריצה, ולכן אפרט על נושא זה.

כמו שאמרתי קודם לכן, סיבוכיות זמן-ריצה נועדה להגדיר זמן מוערך לביצוע אלגוריתם מסויים, והיא עושה זאת לפי מספר הפקודות שעל המחשב לעבד עבור אלגוריתם מסויים. לכן, הפונקציה שתחשב את הסיבוכיות, תאסוף בעצם את כל הפקודות בתכנית לסכום שיהיה תלוי בקלט של האלגוריתם.

נלך על דוגמה ראשונה. נניח שיש לך האלגוריתם הבא:
1. עבור i מ-1 ועד n בצע:
1.1. הדפס "Hello".

האלגוריתם הנ"ל מדפיס למסך את המחרוזת Hello כפול x פעמים, כלומר אם נתייחס לפעולת ההדפסה כאל פקודה כללית, הרי שהמחשב יבצע x פקודות.
אם נייחס לאלגוריתם הנ"ל פונקציה שתנפיק את מספר הפעולות שיבוצעו, הפונקציה תיראה כך: f(x) = x, ולכן נאמר שסיבוכיות זמן הריצה של האלגוריתם הנ"ל היא (O(n.
האמת שאין לי מושג למה בחרו ב-O כדי לייצג סיבוכיות, ואף פעם לא טרחתי לבדוק את זה, כמו גם המשתנה n.

דוגמה שנייה:
1. עבור i מ-1 ועד x בצע:
1.1. עבור j מ-1 ועד y בצע:
1.1.1. חשב temp = i * j.
1.1.2. הדפס את temp.
1.1.3. הדפס " ". (רווח למי שלא הבין)

האלגוריתם הנ"ל מדפיס למסך מעין "לוח-כפל" אשר תחום בגבולות הקלט x ו-y. נחשב את מספר הפעולות הכלליות שהאלגוריתם יבצע, ונקבל:
f(x,y) = x * y * 3, ולכן נאמר שסיבוכיות זמן-הריצה של האלגוריתם הנ"ל היא (O(n^2.
למה?
מכיוון ש-x ו-y נבחנים כגורמי קלט כלליים, והם "מומרים" להיות קלט-כללי (כל אחד בנפרד) אשר לפי סיבוכיות זמן-הריצה יהיה n.
אז מדוע נשמטה הכפולה ב-3?
משום שהכפולה ב-3 חסרת משמעות במקרה שלנו. 3 הינו מספר קבוע אשר לא יהיה תלוי בשום גורם קלט.
תבין, כשמדברים על סיבוכיות, מנסים לראות את האלגוריתם בפרספקטיבי של גודל אינסופי של הקלט (או גודל גדול מאוד), כך שאם n יהיה אינסוף (בהגזמה), אז 3*n יהיה גם-כן אינסוף, כלומר השינוי לא משמעותי מכדי שנצרף אותו לסיבוכיות זמן-הריצה.

עוד דוגמה למצב הקודם:

1. עבור i מ-1 עד x בצע:
1.1. עבור j מ-1 ועד y בצע:
1.1.1. חשב temp = i * j.
1.1.2. הדפס את temp.
1.1.3. הדפס " ".
1.2 רד שורה (כמו אנטר, 'n\' וכו'...).

הפונקציה חכאן תהיה: (f(x,y) = y * 3 * (x + 1.
לאחר המרת הקלט ל-n ולאחר הסרת הקבועים, נקבל, כמה מפתיע, (O(n^2. כמו מקודם. בטח שמת לב, שבכל מקרה של לולאות מקוננות פשוטות, סיבוכיות זמן הריצה תהיה תלויה רק במספר הלולאות המקוננות.

אני לא אפרט עוד על המקרים הקצת-יותר מסובכים של סיבוכיות. אני רק אומר שבלבול-המוח של המורה שלך על (log(n (פונקציה לוגריתמית) קשורה בד"כ (לפחות במקרים הראשונים הנלמדים בבי"ס) לחיפוש בינארי במערך או למיון בעץ בינארי וכו'. פה נכנסת קצת מתימטיקה, ואני לא בא ללמד אותך את זה.