retagged by
4,134 views
26 votes
26 votes
Express $T(n)$ in terms of the harmonic number $\displaystyle H_{n}= \sum_{i=1}^{n} \frac{1}{i},\quad 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$ ?
retagged by

2 Answers

Best answer
40 votes
40 votes
$T(n) = \frac{n+1}{n}T(n-1) + 1\qquad\qquad \to(1)$

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

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

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

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

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

Now substituting value of $T(n-2)$ in above equation

$\implies 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$

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

$\displaystyle{\vdots}$

so on

$T(n) = \frac{n+1}{n-k+1}T(n-k) + \frac{n+1}{n} + \frac{n+1}{n-1} + \ldots + \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} +\ldots+ \frac{1}{n-k+2}) + 1$

Now let $n-k=1$ so $k = n-1$, substitute value of $k$ in above equation

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

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

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

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

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

Now, $H_n \approx \log n+γ$

where $γ$ is the Euler-Mascheroni constant.

$\mathbf{T(n) = O(n \log n)}$
edited by
4 votes
4 votes

Using subtract and conquer method, easly we can solve such type of questions .

Related questions

7 votes
7 votes
1 answer
1
makhdoom ghaya asked Nov 25, 2016
2,381 views
Consider a hash table with chaining scheme for overflow handling:What is the worst-case timing complexity of inserting $n$ elements into such a table?For what type of ins...
13 votes
13 votes
3 answers
4