Je možné vysvetliť, čo znamená časová zložitosť algoritmu rovná O(n)?

Časová zložitosť algoritmu, rovná O(n), znamená, že čas vykonávania algoritmu rastie lineárne s rastom veľkosti vstupných údajov n. Ak sa počet prvkov zdvojnásobí, doba spracovania sa približne zdvojnásobí.

Napríklad, ak máte slučku, ktorá prechádza všetky prvky poľa s n prvkami, ide o typický prípad O(n):

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

Tu závisí doba vykonávania priamo od počtu prvkov v poli.