GATE CSE
First time here? Checkout the FAQ!
x
0 votes
160 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$?
closed as a duplicate of: GATE1990-17a
asked in Algorithms by Veteran (38.8k points)  
closed by | 160 views

1 Answer

+2 votes

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)*(Hn - $\frac{1}{2}$ - 1) + 1

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

T(n) = (n+1)*Hn - n

Now Hn≈logn+γ

where γ is the Euler-Mascheroni constant. 

T(n) = O(nlogn)

answered by Boss (7.9k points)  
edited by


Top Users Sep 2017
  1. Habibkhan

    6970 Points

  2. Warrior

    2490 Points

  3. Arjun

    2368 Points

  4. rishu_darkshadow

    2136 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. makhdoom ghaya

    1760 Points

  8. manu00x

    1750 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,060 questions
33,668 answers
79,747 comments
31,079 users