בשאלה יש לי שתי לולאות אחת בתוך השנייה, אבל לא שתיהם מתחילות מ 1 עד N , אלא הלולאה הפנימית תלוייה באינדקס של החיצונית..
אז אפשר להגיד פשוט שזה O(n^2) ?? כי בפועל נראה לי שזה לוקח פחות ? מה הדרך לחשב
:מן הסתם אתה עושה 1+2+...+n ריצות כאלו בתוך הלולאות. הסכום של כל אלו הוא n*(n+1)/2 שזה (O(n^2 עד כדי קבועים (הכוונה היא שזו בדיוק הסיבוכיות, ולא חסם מלמעלה כמו ש big O בד"כ מסמן). כמובן שים לב שבכל אחת מ n^2 הפעולות אתה לא באמת עושה עבודה רק של (O(1. אשאיר לך לחשוב על זה.