1,972 views

2 Answers

0 votes
0 votes
It should be n^2.

Because t(n/2) part only goes till logn depth but t(n-1) part goes till ndepth and cost of each stage is equal to size of problem at that level.

so,t(n)=1+2+3+4+5+....+n=O(n^2)
0 votes
0 votes

I used Back substitution method for solving this particular problem. you can see the attached image.

The answer according to my approach is O(n^2).

EDIT- in the below image,read f(n) = n(n+1)/2  (in last third line)

Related questions

2 votes
2 votes
0 answers
1
Rajeev Kumar 1 asked Jan 9, 2018
760 views
T(N)=3T((N/3)+5)+N/2what will be the time complexity?
0 votes
0 votes
1 answer
3
Parshu gate asked Sep 13, 2017
286 views
HOW ARE C1,C2 VALUES CALCULATED ?
0 votes
0 votes
3 answers
4
Anmol Verma asked Jan 9, 2017
1,463 views
1) T(n)=T(n-1)+1/n.2) T(n)=T(n-1) +1/log(n)3)T(n)=3T((n/3) - 2)+n/2.4)T(n)=T(n/2)+T(n/4)+T(n/8)+n.Use Masters theorem