Solve The Recurrance

Question

Solve the following Recurrence Equation using back substitution method

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

Answer 1

Here Answer should be O(nlogn)

lets see how!

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

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

T(n) = T(n-2) +logn +log(n-1) using 2nd.

T(n-2) = T(n-3) + log(n-2)             ---3

T(n) = T(n-3) +logn +log(n-1)+log(n-2)

so by following this pattern we can write

T(n) = T(n- (n-1)) + log 1 + log 2+ log3+ ............+ log(n-1) +logn

as we know logn +log(n-1) = log(n)(n-1)

therefor T(n) = T(1) + logn.(n-1).(n-2)......3.2.1

T(n) = T(1) + logn!

and log n!<= nlogn

therefor this is O(nlogn)