Jaką złożoność ma ten prosty program?

Witam, jaką złożoność ma ten prosty program? N^2?

for(int i=1;i<=n;i++){
        for(int j=i;j>=1;j--){
            licznik++;
    }

Oczywiście, że kwadratową.

(n+1)*n/2 daje wynik tej pętli czyli ile razy się te dodawanie doda.
Nie jestem pewny, ale to powinno być złożonością tego algorytmu.

Czyli jak wywalisz tą pętlę to ten wzór ci zastąpi te proste inkrementowanie w pętli, w sumie to to samo, ale niestety nie byłem na studiach informatycznych i nie jestem pewny swojej definicji.

PretzPrecialy napisał(a):

(n+1)*n/2 daje wynik tej pętli czyli ile razy się te dodawanie doda.

Dlaczego n+1? Główna pętla wykona się dokładnie n razy, bo zaczyna od 1, a kończy na n, ze względu na operator <=. Tak więc ogólnie pisząc, dokładna liczba iteracji zagnieżdżonej pętli wynosi n*n/2.

Edit: Jednak poprzednik podał dobry wzór – (n+1)*n/2 iteracji.

Jako ciekawostka: formalnie jest to złożoność kwadratowa, ale kompilator jest na tyle cwany, że wychodzi czas stały dla clang: https://godbolt.org/z/D11R8H albo liniowy dla gcc: https://godbolt.org/z/TACX23 i msvc: https://godbolt.org/z/MVAc3B

Żeby pisać o złożoności obliczeniowej to warto podać co jest uznawane za operację dominującą i o jaki zasób chodzi. Można się domyślać, że chodziło o inkrementacje ... wtedy mamy kwadratową.
Ale można się też domyśleć, że chodziło o zajętość pamięci lub liczbę zapisów na dysk. Wtedy stała, albo nawet 0 :-)