Re: hey help in solving the following recurrence...


On Jan 28, 9:13 pm, "sarah" <sarahsmit...@xxxxxxxxx> wrote:
hi can yu hep me solve the following recurrence,

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

T(2) and T(1) are constants...

If you expand it out (assuming T(0) = 0):

T(n) = T(n-1) + lg n
= T(n-2) + lg(n-1) + lg n
...
= lg 1 + lg 2 + ... + lg n
= lg (n!)
= Theta(n log n)

.