Lze vysvětlit, co znamená časová složitost algoritmu rovná se O(n)?

Časová složitost algoritmu, rovná O(n), znamená, že doba běhu algoritmu roste lineárně s velikostí vstupních dat n. Pokud se počet prvků zdvojnásobí, doba běhu se přibližně zdvojnásobí.

Například pokud máte cyklus, který prochází všechny prvky pole s n prvky, jedná se o typický případ O(n):

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

Zde doba běhu závisí přímo na počtu prvků v poli.