חישוב סיבוכיות הזמן של תוכנית נתונה

[marbd]

נתונה התוכנית הבאה בשפת C:

int i,j,k;
for(i = 1; i <= n; i++) {
	for(k = 1; k <= i; k++) {
		j = k;
		while(j > 0) {
			j--;
		}
	}
}

חשבו את סיבוכיות הזמן של התוכנית התונה. חובה לפשט את הביטוי ככל שניתן.
אני מנסה לחשב את סיבוכיות הזמן של התוכנית אבל אני לא מצליח להבין כיצד לעשות זאת באופן פורמלי.
אשמח לעזרה

[Ben]

כדי לחשב את סיבוכיות הזמן של התוכנית הנתונה, נבצע את החישוב הבא:

\begin{align*} \sum_{i=1}^{n}\sum_{k=1}^{i}\sum_{j=1}^{k}1&\overset{(1)}{=}\sum_{i=1}^{n}\sum_{k=1}^{i}(k-1+1)=\sum_{i=1}^{n}\sum_{k=1}^{i}k\\&\overset{(2)}{=}\sum_{i=1}^{n}\frac{i(i+1)}{2}=\frac{1}{2}\cdot\sum_{i=1}^{n}i^{2}+\frac{1}{2}\sum_{i=1}^{n}i\\&\overset{(2)}{=}\frac{1}{2}\cdot\sum_{i=1}^{n}i^{2}+\frac{n(n+1)}{4}\overset{(3)}{=}\frac{1}{2}\cdot\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{4}\\&=\frac{n(n+1)}{12}\cdot\left[(2n+1)+3\right]=\frac{n(n+1)(2n+4)}{12}\\&=\frac{n(n+1)(n+2)}{6}=O(n^{3}) \end{align*}

הסבר על המעבר הראשון - ע"פ הזהות:

\sum_{i=m}^{n}1=n-m+1

הסבר על המעבר השני - ע"פ הזהות:

\sum_{i=0}^{n}i=\sum_{i=1}^{n}i=\frac{n(n+1)}{2}

הסבר על המעבר השלישי - ע"פ הזהות:

\sum_{i=0}^{n}i^{2}=\sum_{i=1}^{n}i^{2}=\frac{n(n+1)(2n+1)}{6}

סה"כ נוכל להסיק כי סיבוכיות הזמן של התכונית הנתונה הינה O(n^3).
בהצלחה