שלום,

אם נתונה הפונקציה:

fun_c

for (i=10; i<1.2^n; i*=1.2

{}

חקרתי קצת את הפונקציה והיא עובדת עבור n>=13

אבל לא הצלחתי להבין מה הסיבוכיות שלה.

למישהו יש רעיון?

תחשוב מה הערך של i כתלות במספר האיטרציות.

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

חשבתי ככה, אבל זה היה טיפה מוזר כי יצאה לי סיבוכיות O(n)

אבל עבור מ=13 מתבצעת איטרציה אחת ולא 13 איטרציות זה הגיוני?

לא כזה מוזר, זו אכן הסיבוכיות

סיבוכיות (O(n לא אומרת שיתבצעו בדיוק n איטרציות, אלא שמספר האיטרציות חסום ע"י קבוע כלשהו כפול n.

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

ישששששש תודה רבה!!!!