רציתי לדעת מהם הכללים לצמצום נוטציות של O גדול כך שהחסם עדיין נחשב הדוק באופן סביר. הסבר:
ידוע לנו כי
O(2+n) = O(n)
O(n+n2) = O(n2)
אבל מה קורה כשמדובר בפונקציה אקספוננציאלית? האם גם אז תקפים הכללים ל"השמטה" של החזקה הגבוהה ביותר, כפי שהודגם בכיתה? לדוגמא:
1. O(2n + n7) =?= O(2n)
2. O(n*2n+2 + n5) =?= O(n*2n) =???= O(2n)
נביט על המקרים השונים:
1. במקרה הראשון המקדם האקספוננציאלי נפרד מהמקדם הפולינומינאלי - במקרה זה נראה לי די ברור שאכן O(2n) - ההשפעה של n בשביעית פה דומה להשפעה של חזקה נמוכה יותר בצירוף עם חזקה גבוהה, וכך החזקה השביעית "נבלעת" בביטוי האקספוננציאלי.
2. בשיוויון הראשון למעשה מבוצעת אותה פעולה כמו ב(1). אבל בשיוויון השני =???= השמטתי את n. כאן אני פחות בטוח - הרי אנחנו שומרים על logn בביטוי O(nlogn) - וזאת למרות שברור שגידול ליניארי כמו n גדול משמעותית מגידול לוגריתמי. הרי מה שיש לנו פה הוא פונקציה של n עם מקדם logn - זהו זמן ריצה שהוא גבוה יותר מO(n) אבל עדיין נמוך מO(n2).
השאלה, אם כן, האם ראוי לא לצמצם את הביטוי n*2n? ולראות בו בעצם פונקציה של 2n עם מקדם קטנטן של n?