Meg lehet magyarázni, mit jelent az algoritmus időbeli összetettsége, ami O(n)?

Egy algoritmus időbeli komplexitása, amely egyenlő O(n)-nel, azt jelenti, hogy az algoritmus futási ideje lineárisan növekszik a bemeneti adatok méretével n. Ha a elemek száma megduplázódik, akkor a futási idő körülbelül megduplázódik.

Például, ha van egy ciklus, amely végigmegy az n elemű tömb összes elemén, ez egy tipikus O(n) eset:

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

Itt a futási idő közvetlenül függ a tömb elemeinek számától.