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. con rapporto 1/2 e il numero totale di termini è logn, quindi usando la formula della somma di n termini di G.P. otterremo:-

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

T(n) + n((1 - 1/n)/ 1/2) { poiché 2^logn è uguale a n}

Siccome 1/n si avvicina a 0, quindi ignorandolo, otteniamo

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

T(n) = 2n +1

T(n) = O(n) {nelle notazioni asintotiche ignoriamo le costanti}

Nota: Ci sono altri metodi per risolvere come il teorema di Master. Ma funziona solo in alcuni casi speciali e in altri casi dà risposte sbagliate. Perciò raccomando di usare solo il metodo di sostituzione.