שאלת מבחן במבוא למדעי המחשב - אוניברסיטת בר-אילן 2023 - סיבוכיות זמן

מה מספר הפעולות שמבוצעות בקוד הבא (כפונקציה של $n$), ומה הסיבוכיות (ב-$\Theta$) שלה? ```c int f(int n) { int v = 0; for(int i=0;i<n;i++) for(int j=0;j<i;j++){ v+=2; if(!(i^(n*n))) break; } return v; } ```

רמז: `!(i^(n*n))` הוא true רק כאשר $i = n^2$. אבל $i < n$, ולכן $i$ לעולם לא שווה ל-$n^2$ (עבור $n > 1$). ה-break לא מתבצע לעולם.

פתרון: `!(i^(n*n))` is true only when $i = n^2$. Since $i < n$ and $n^2 > n$ for $n > 1$, the **break never executes**. לכן: לולאה כפולה סטנדרטית $\sum_{i=0}^{n-1} i = \frac{n(n-1)}{2}$. $$\boxed{f(n) = \Theta(n^2)}$$ $\blacksquare$