Ar galima paaiškinti, ką reiškia algoritmo laiko sudėtingumas, lygus O(n)?

Algoritmo laiko sudėtingumas, lygus O(n), reiškia, kad algoritmo vykdymo laikas auga linijiniu būdu su įvesties duomenų dydžiu n. Jei elementų skaičius padvigubėja, darbo laikas taip pat maždaug padvigubėja.

Pavyzdžiui, jei turite ciklą, kuris pereina per visus n elementų masyvo elementus, tai yra tipiškas O(n) atvejis:

void PrintElements(int[] arr) {
    for (int i = 0; i < arr.Length; i++) {
        Console.WriteLine(arr[i]);
    }
}

Čia vykdymo laikas tiesiogiai priklauso nuo masyvo elementų skaičiaus.