T(n) = T(n-1) + 10/n

Question

What I have done so far is:

T(n-1) + 10/n

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

T((n-2)-1) + 10/(n+2) + 10/(n+1) + 10/n =  T(n-3) + 10/(n+2) + 10/(n+1) + 10/n

Assume n-k = 1,

So... I get lost here,

T(n-k) + ??

Answer 1

well what i understand is:

T(n) =T(n-1) + 10/n

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

T(n-2)=T(n-3) + 10/(n-2)

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

T(n) =T(n-3) + 10/(n-2) + 10/(n-1) + 10/n

similarly,

T(n) =T(n-k) + 10/(n-k) + 10/(n-k+1) + 10/(n-k+2)+......... + 10/n

for n-k=1:

T(n) =T(1) +10*(1/1 + 1/2 + 1/3 + ................1/n )

so, (1/1 + 1/2 + 1/3 + ................1/n ) is a harmonic progression its sum cant be found perfectly but its proportional to log(n).

so, T(n) is of order of log(n).

sum of harmonic progression:click here

Answer 2

Let's assume the boundary condition T(1)=1, otherwise the recurrence is not well defined.

You can write the recurrence out:

T(n) = T(n-1) + 10/n = T(n-2) + 10/(n-1) + 10/n
     = ...
     = 10 * (1/n + 1/(n-1) + ... + 1)
     = 10 * H_n,

where H_n is the n-th Harmonic number. It is very well-known that H_n=Theta(log n). (You can prove this by noting that log n = integral from 1 to n 1/n dn and that the sum 1 + 1/2 + ... + 1/n is bounded from above by that integral.)

Hence T(n) = Theta(log n).