[Algorytmy] Liczba wykonań instrukcji oraz rząd f(n)

[valverde12345]

Zad 2: Niech \(\displaystyle{ f(n)}\)dla n\(\displaystyle{ \ge 1}\), bedzie liczba wykonan instrukcji \(\displaystyle{ S}\). Podaj ile wynosi \(\displaystyle{ f(n)}\) oraz jakiego jest rzedu.

1: for \(\displaystyle{ i \leftarrow 1, n-1}\) do
2: for \(\displaystyle{ j \leftarrow 1, n-i}\) do
3: \(\displaystyle{ S}\)
4: end for
5: end for

dla n=1: 0
dla n=2: 1
dla n=3: 3
dla n=4: 6

Wiec mozna to zapisac wzorem \(\displaystyle{ f(n)= \sum_{i=1}^{n}n-i}\)
Co do rzedu to nie jestem pewien : \(\displaystyle{ O(n ^{2} -2)}\)

[bartek118]

Rozpisz tę sumę:
\(\displaystyle{ f(n)= \sum_{i=1}^{n}n-i = \sum_{i=1}^n n - \sum_{i=1}^n i = n^2 - \frac{n^2 + n}{2} = \frac{n^2 - n}{2}}\)
Czyli faktycznie mamy \(\displaystyle{ f(n) = \Theta (n^2)}\).