Complexidade é um assunto - sem trocadilho - complexo. Mas pra resumir, não é necessariamente sobre tempo, e sim sobre "quantidade de operações de acordo com o tamanho da entrada". E tanto n quanto n + 1 são ambos O(n), o termo mais significativo prevalece. Para valores grandes de n, esse 1 a mais se torna insignificante e é descartado.

Tem explicações bem detalhadas aqui e aqui. Sugiro que leia tudo.