Pode explicar o que significa a complexidade temporal de um algoritmo igual a O(n)?

A complexidade temporal de um algoritmo, igual a O(n), significa que o tempo de execução do algoritmo aumenta linearmente com o aumento do tamanho dos dados de entrada n. Se o número de elementos duplicar, o tempo de execução também aproximadamente duplica.

Por exemplo, se tiver um ciclo que percorre todos os elementos de um array de n elementos, esse é um caso típico de O(n):

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

Aqui, o tempo de execução depende diretamente do número de elementos no array.