retagged by
7,047 views

1 Answer

1 votes
1 votes
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)

Related questions

2 votes
2 votes
4 answers
2
Anjana Babu asked Dec 31, 2016
1,137 views
On solving the RecuranceT(n) = 3T(n/4) + cn2I was stuck at summation$\sum_{i=0}^{log_4 n} (\frac{3}{16})^{i} cn^{2}$Can someone could help ?
3 votes
3 votes
2 answers
3
pC asked Jan 15, 2016
497 views
an = an-1 + n , n>=1a0=2Find a100... ?SolutionI actually wanted to know what is wrong with this method .Could you pls help Whats wrong here .T(n) = T(n-1)+nand back su...
3 votes
3 votes
2 answers
4
Diksha Aswal asked Jul 3, 2017
1,859 views
T(n) = T(n/3)+T(2n/3)+n What is the solution of Above Given recurrence relation?Give full method to solve this