#include <stdio.h>
#include <stdlib.h>

/*
Co oznacza zlozonosc algorytmu O(1)?

-> oznacza ze taki algorytm dla różnej ilości przyjmowanych danych wykonuje zawsze stałą liczbę operacji
-> np. w tym przypadku wykonywana jest jedna operacja - wykorzystanie wzoru na ciąg arytmetyczny w celu obliczenia sumy
-> ważne jest to, że dla różnych danych liczba operacji się nie zmienia - to jest klucz w zrozumieniu tego
-> Algorytm o złożoności oznaczonej O(1) jest najszybszym z możliwych - bo nieważne czy podłożymy milion liczb czy jedną - będzie zawsze działać tak samo szybko

Dlaczego w tym algorytmie jest O(1)?
- bo jest stała liczba operacji - tutaj akurat jedna
*/

/*
Co oznacza zlozonosc algorytmu O(n)?

-> oznacza, że liczba operacji w takim algorytmie nie jest STAŁA w zależności od ilości przyjmowanych danych
-> im więcej danych tym rośnie liczba operacji, no bo jest pętla wiadomka
-> można powiedzieć, że ten algorytm jest LINIOWY - bo liczba operacji rośnie proporcjonalnie do ilości przyjmowanych danych

Dlaczego w tym algorytmie jest O(n)?
- w tym algorytmie wykonujemy następujące operacje:
    1) przypisanie int sum=0;
    2) Odpalenie pętli N razy, więc mamy N operacji
    3) return sum - ostatnia operacja
    Łącznie wychodzi: f(N) = 1 + N + 1 = N +2
    Złożoność jest to ograniczenie z góry funkcji. Więc pomijamy stałe.
    Zatem złożoność tego algorytmu wychodzi nam : O(N)
*/

//sumowanie liczb z wykorzystaniem wzoru na sumę wyrazow w ciagu arytmetycznym - O(1)
int sum1(int n) {
  return  (n * (n+1))/2;
}

//sumowanie liczb w petli - O(n)
int sum2(int n) {
  int sum = 0; //1 operacja
  for (int i = 1; i <= n; i++) { //n operacji
    sum += i;
  }
  return sum; //2 operacja
}

//sumowanie liczb - budujemy macierz NxN wypełnioną liczbami od 1 do N. Macierz ma n^2 komórek, przez
//które przechodzimy w dwóch pętlach, a nastepnie wyznaczamy sumę
//ponieważ przechodzimy przez każdą komorke macierzy to zlozonosc bedzie O(n^2)
int sum3(int n){
    int sum=0;
    int array[n+1][n+1];

    int j,i;
    for (i = 1; i <= n; i++) {
        for (j = 0; j <= n; j++) {
                array[i][j] = i;

        }
        sum+=array[i][0];

    }
return sum;
}

int main(){
    printf("sum1: %d", sum1(5));
    printf("\nsum2: %d", sum2(5));
    printf("\nsum3: %d", sum3(5));

    return 0;
}