GATE CSE 1990 | Question: 17a

Question

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$ ?

Comments

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!

---

@mcjoshi, please correct equation 1, i think it should be (n+1) / n instead of (n+1) / 2..!

---

Ohh, I solved some other recurrence. Thanks for pointing it out :)

---

T(n)= ((n+1)/n) T(n-1) + 1   for  $n>=\sum$

 

n>= summation what it means??

can anybody help!

 

 

Answer 1

$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)}$

Comments

Great answer.

---

Why isn't the n+1 term substituted in terms of k?

Edit : 😅 Oh my bad, its not changing, its constant

---

can some on explain me this clearly what is happening after  that SO ON in the solution

---

“Hn≈logn+γ” from where did we concluded this?

Answer 2

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

Comments

@Divyanshu ,it is constants , right ? means , we don't have to take only 'c' as constant..here , all a,b,c,k all are constants.

and If possible , Please provide the pic of the whole method from that book.

---

don't know how to upload pic here they are asking bla bla bla.... it is not that easy like fb

---

Hahaha...