For GATE this should be sufficient I guess. It is hard to do better.

Dark Mode

admin
asked
in Algorithms
Oct 6, 2015

735 views
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

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

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