O que significa T(n) em relação a O(n)?

Ao discutir um algoritmo, o uso comum do símbolo [matemática]T[/math] é para representar sua complexidade temporal.

[matemática]T[/math] é uma função. O input para esta função é o tamanho do input, o output é o (pior dos casos) tempo de execução para um input desse tamanho.

Por isso, [matemática]T(n)[/math] é um número: o número retornado pela função [matemática]T[/math] quando dado o número [matemática]n[/math]. Este número é o tempo de execução do nosso algoritmo em uma entrada de tamanho [matemática]n[/math].

O [matemática]O[/math] em "[matemática]O(n)[/math]" não é uma função. Esta é uma notação do Big O. Em particular, o símbolo [matemática]O(n)[/math] representa a classe de todas as funções que crescem (assintóticamente) tão rapidamente quanto a função linear [matemática]f(n)=n[/math].

Big O notation nos dá uma maneira conveniente de falar sobre limites superiores. Por exemplo, podemos dizer "a complexidade temporal deste algoritmo é [matemática]O(n^2)[/math]" (formalmente: "[matemática]T\ em O(n^2)[/math]") para dizer que o tempo de execução do algoritmo é no máximo quadrático no tamanho de entrada.

Por vezes, você pode ver ambos os símbolos sendo usados em uma única equação. Por exemplo, a complexidade temporal do MergeSort é normalmente descrita pela seguinte recorrência: "[matemática]T(n) = 2T(n/2) + O(n)[/math]".

O significado da afirmação acima: Para qualquer [matemática]n[/math], o tempo [matemática]T(n)[/math] necessário para ordenar elementos [matemática]n[/math] pode ser calculado tomando o tempo [matemática]T(n/2)[/math] necessário para ordenar elementos [matemática]n/2[/math], multiplicando esse tempo por 2, e adicionando algo extra. Que algo extra deve ser, no máximo, linear em [matemática]n[/math].