לוח מובילים

יש פה רק פונקציה אחת, שלא קוראת לעצמה, אז נוכל נחלק את הבעיה לשתיים: סיבוכיות הזמן של הלולאה הראשונה ("כמה זמן לוקח לה לרוץ") - ניתן לנתח את זה, ואני אשתדל לערוך את ההודעה מאוחר יותר ולהביא את הניתוח, אבל כרגע אני אבטיח לך (כי פתרתי את השאלה ממקודם) שהסיבוכיות פה תצא קטנה מבלולאה השנייה, ולכן מה שהולך לצאת בלולאה השנייה הוא הדומיננטי והקובע. מה שכן חשוב לשים פה לב, זה שהתנאי של הלולאה הוא x^2>n, ובכל איטרציה מקטינים את x. במילים אחרות, ברגע ש-x יהיה מסדר גודל של שורש n, נצא מהלולאה (x יכול להיות שווה ל(שורש n) או קצת קטן יותר, זה לא חשוב לנו, כי זה עדיין סדר גודל של (שורש n) ולכן x^2 שווה ל-n, אולי קצת קטן יותר, וזה בדיוק התנאי ליציאה מהלולאה). סיבוכיות הזמן של הלולאה השנייה - אז יצאנו מהלולאה, והערך של x הוא כעת מסדר גודל של שורש n. נשים לב כי לולאה זו רצה x פעמים, כלומר היא תרוץ סדר גודל של שורש n פעמים, ולכן סיבוכיות הזמן היא http://www.codecogs.com/gif.latex?O(%5Csqrt%7Bn%7D). אגב נדמה לי שבפייסבוק היה דיון על השאלה הזאת (טוב משם לקחת את התמונה...).

מצורף