The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
219 views
Express $T(n)$ in terms of the harmonic number $H_{n}= \sum_{t=1}^{n} 1/i, n \geq 1$, where $T(n)$ satisfies the recurrence relation,

$T(n)=\frac{n+1}{n} T(n - 1)+1$, for $n \geq \sum$ and $T(1) = 1$

What is the asymptotic behaviour of $T(n)$ as a function of $n$ ?
asked in Algorithms by Veteran (42k points)
edited by | 219 views

the n-th harmonic number is the sum of the reciprocals of the first n natural numbers.

https://en.wikipedia.org/wiki/Harmonic_number

And Using Back-Substitution it can be found out that $T(n) = O(n^n)$
Please solve it .

Hope it Helps!

1 Answer

+5 votes
Best answer

$T(n) = \frac{n+1}{n}T(n-1) + 1$ --------------------------------------------------(1)

$T(n-1) = \frac{n}{n-1}T(n-2) + 1$--------------------------------------------(2)

$T(n-2) = \frac{n-1}{n-2}T(n-3) + 1$--------------------------------------------(3)

substituting value of $T(n-1)$ from eqn (2) in eqn (1)

$T(n) = \frac{n+1}{n}*\frac{n}{n-1}T(n-2) + \frac{n+1}{n} + 1$

$T(n) = \frac{n+1}{n-1}T(n-2) + \frac{n+1}{n} + 1$

now substituting value of $T(n-2)$ in above eqn

$T(n) =  \frac{n+1}{n-1}* \frac{n-1}{n-2}T(n-3) + \frac{n+1}{n-1} + \frac{n+1}{n} + 1$

$T(n) =  \frac{n+1}{n-2}T(n-3) + \frac{n+1}{n-1} + \frac{n+1}{n} + 1$
.
.
.
.

so on

$T(n) = \frac{n+1}{n-k+1}T(n-k) + \frac{n+1}{n} + \frac{n+1}{n-1} + ...... + \frac{n+1}{n-k+2} + 1$

$T(n) = \frac{n+1}{n-k+1}T(n-k) + (n+1)*( \frac{1}{n} + \frac{1}{n-1} +.....+ \frac{1}{n-k+2}) + 1$

now let $n-k=1$ so $k = n-1$, substitute value of $k$ in above eqn

$T(n) = \frac{n+1}{n-(n-1)+1}T(1) + (n+1)*( \frac{1}{n} + \frac{1}{n-1} +.....+ \frac{1}{n-(n-1)+2}) + 1$

$T(n) = \frac{n+1}{2} + (n+1)*( \frac{1}{n} + \frac{1}{n-1} +.....+ \frac{1}{3}) + 1$

$T(n) = \frac{n+1}{2}+ (n+1)*(H_n - \frac{1}{2} - 1) + 1$

$T(n) = \frac{n+1}{2} + (n+1)*H_n - \frac{n+1}{2} - (n+1) + 1$

$\mathbf{T(n) = (n+1)*H_n - n}$

Now $H_n \approx \log n+γ$

where $γ$ is the Euler-Mascheroni constant. 

$\mathbf{T(n) = O(n \log n)}$

answered by Boss (8.7k points)
edited by


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,831 questions
36,676 answers
90,577 comments
34,638 users