algorithm

Question

finf the tc

T(n)=nlogn +T(n-1)

Answer 1

It's very simple, Check this.

T(n) = T(n-1) + $ n log n$

If you expand this then you get

T(n) = $ 1 log 1 + 2 log 2 + 3 log 3 + 4 log 4 + ........ + (n-1) log (n-1) + n log n $

T(n) <= $ n log n + n log n + n log n + n log n + ........ + n log n + n log n $

T(n) <= $ n * (n log n) $

T(n) <= $ n^2 log n $

T(n) = $ O (n^2 log n) $

Comments

CAN YOU TELL ME ABOUT EXPANSION , I AM UABLE TO GET IT

Answer 2

T(n)=T(n-1)+nlogn

expand by substitution..

T(n)=T(n-k)+(n-(k+1))log(n-(k+1))+.........+(n-3)log(n-3)+(n-2)log(n-2)+(n-1)log(n-1)+nlogn

     =T(n-k)+(nlog(n-(k+1))+.......+nlog(n-3)+nlog(n-2)+nlog(n-1)+nlogn) - (1log(n-1)+2log(n-2)+3log(n-3)+......+(k+1)log(n-(k+1)))

      =T(n-k)+n(log(n*(n-1)*(n-2)*......3*2*1)-{something }

      =nlog(n^n)

     =O(n^2logn)