retagged by
282 views

1 Answer

0 votes
0 votes

You can solve it using substitution method.

Here base condition T(1)=0 must be given

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

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

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

.

By substituting..

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

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

T(n) = T(1) + log (n * (n-1) * (n-2) * (n-3) ..... (n-(n-2))            [multiplication goes upto (n-1) times]

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

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

T(n) = O(nlogn)

Related questions

2 votes
2 votes
1 answer
1
3 votes
3 votes
2 answers
2
1 votes
1 votes
2 answers
3