recurrence relation-iteration method

Asked Nov 21 '17 at 12:25

Active Nov 21 '17 at 12:25

Viewed 43 times

I want to solve this recurrence relation:

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

I have tried this: $T(n-1)=T((n-1)-1)+ \frac{n-1}{log(n-1)} + \frac{n}{log(n)}=T(n-2)+\frac{n-1}{log(n-1)}+\frac{n}{log(n)}$

Hence, $T(n-i)=T(n-i-1)+\sum_{k=0}^i\frac{n-k}{log(n-k)}$.

$n-i=1=>i=n-1$.

$T(1)=T(n-(n-1)-1)+\sum_{k=0}^{n-1}\frac{n-k}{log(n-k)}=T(0)+\sum_{k=0}^{n-1}\frac{n-k}{log(n-k)}$.

I don't know how to proceed. any suggestion?

asked Nov 21 '17 at 12:25

joe

Do you have an initial condition? – Math1000 Nov 21 '17 at 13:21
HI! this is T(1)=1 – joe Nov 21 '17 at 14:16
By induction it's clear that $$ T(n) = 1 + \sum_{k=2}^n \frac k{\log k},\ n\geqslant 2, $$ but I don't know of any closed form for that sum. – Math1000 Nov 21 '17 at 14:27
1

@Math1000 There is no closed form but one can deduce the equivalent $$T(n)=\Theta\left(\frac{n^2}{\log n}\right)$$ – Did Nov 21 '17 at 17:30

0 Answers0