GATE CSE
First time here? Checkout the FAQ!
x
0 votes
102 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 (29.2k points)  
closed by | 102 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.8k points)  
edited by


Top Users Apr 2017
  1. akash.dinkar12

    3508 Points

  2. Divya Bharti

    2542 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Shubham Sharma 2

    1610 Points

  7. Debashish Deka

    1588 Points

  8. Arunav Khare

    1454 Points

  9. Kapil

    1424 Points

  10. Arjun

    1420 Points

Monthly Topper: Rs. 500 gift card

22,076 questions
28,040 answers
63,230 comments
24,135 users