Можно ли объяснить, что означает временная сложность алгоритма, равная O(n)?

Временная сложность алгоритма, равная O(n), означает, что время выполнения алгоритма растёт линейно с увеличением размера входных данных n. Если количество элементов увеличивается вдвое, то и время работы примерно удваивается.

Например, если у вас есть цикл, который проходит по всем элементам массива из n элементов, то это типичный случай O(n):

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

Здесь время выполнения зависит напрямую от количества элементов в массиве.