How to get an upper bound for T(n) = T(n/2) + n

Yes your guess is Correct. Its O(n) only. And is the stepwise explanation of the substitution method.

We are a recurrence relation as :-

T(n) = T(n/2) + n

Now solving this through substitution method-

T(n) = T(n/2) +n

T(n) = T(n/2^2) +n/2 + n

T(n) = T(n/2^3) + n/2^2 + n/2 + n

.

.

. k times repeating, we get

T(n) = Tn/2^k + n/2^k-1 n/2^k-2 + …….. + n/2 + n

log(n) times repeating…

T(n) = T(n/2^logn) + n/2^logn-1 + n/2^logn-2 +………+ n/2 + n

Since T(n/2^logn) = T(n/n) {property of log}

T(n/n) = 1; therefore our function becomes:-

T(n) = 1+ n/2^logn-1 + n/2^logn-2 +…………..+ n/2 + n

We can write in reverse order as:-

T(n) = n + n/2 + n/2^2 + ……………… + n/2^logn-1 +1

Taking n common from all the terms, we get:-

T(n) = n(1 + 1/2 + 1/2^2 +………………………+ n/2^logn-1) + 1

Here we get a Decreasing G.P. com razão 1/2 e número total de termos são logn, portanto usando a fórmula de soma de n termos de G.P. obteremos:-

T(n) = n((1 - 1/2^logn)/1-1/2) + 1

T(n) + n((1 - 1/n)/ 1/2) { já que 2^logn é igual a n}

Desde que 1/n está se aproximando de 0, portanto ignorando-a, e obtemos

T(n) = n/(1/2) +1

T(n) = 2n +1

T(n) = O(n) {em notações assimptóticas ignoramos constantes}

Nota: Há alguns outros métodos para resolver, como o teorema do Mestre. Mas ele funciona apenas em alguns casos especiais e em alguns outros casos dá respostas erradas. Portanto recomendarei apenas com o Método de Substituição.