901 views

3 Answers

1 votes
1 votes

I dont know the exact answer but this is my approach.

let the             T(n-1)=T(n/2)                                     T(n/2)=T(n-1)

T(n)=                 2T(n/2)+n    < T(n)=T(n−1)+T(n/2)+n   <  T(n)=2T(n−1)+n

                       Ώ(nlogn)       <           T(n)                   <       O(2n)

so i guess answer should in exponential term for big-Oh.

0 votes
0 votes
I'm not sure. I'm trying to get it right.

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

As we know we Asymptotic notation by equalities and inequalities, we can represent a part of Sub expression in RHS with a Approx Fn.

lets consider T(n/2)+n. By applying masters theorem we get => O(n).

So Our initial Eqn becomes, T(n)= T(n-1)+O(n).  Now if we apply masters theorem we get T(n)= O(n^2).

 

Please Correct me if im wrong
0 votes
0 votes
i can't understand the solution although here. but no specific complexity of the question http://clrs.skanev.com/04/04/05.html its corman solution ite it will be very handy if u r solving coreman http://clrs.skanev.com/04/04/05.html

Related questions

2 votes
2 votes
1 answer
1
0 votes
0 votes
3 answers
3
1 votes
1 votes
1 answer
4