שלום לכולם

רציתי שתעזרו לי להבין מה הסיבוכיות בתרגיל הזה

אני הגעתי למסקנה שזה nlog n (אני נורא לא בטוח בנושא הזה)

תודה לעוזרים

איך הגעת למסקנה שזה nlogn?

יש לך n איטרציות. תחשוב כמה פעולות יש בכל איטרציה (רמז - לא logn).

אוי סליחה אתה צודק אני התבלבלתי

אז זה o(n²) בגלל שהוא רץ על הלולאה פעם אחת(חיצונית)

ובפנימית הוא גם רץ הלולאה n פעמים

בדיוק.

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

בדיוק.

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

תודה על העזרה.

זה בגלל שמסתכלים על המקרה הגרוע ביותר, כן?

לא בדיוק, פשוט מתקיים:

1+2+3+4+...+n = n*(n+1)/2

שזה פשוט (o(n².