Sunday, 27 October 2013

How to prove T(n)=Tleft(fracn4right)+Tleft(frac3n4right)+n is mathcalO(nlogn) using induction?

How would you go about proving the recursion
T(n)=T(n4)+T(3n4)+n

is O(nlogn) using induction?



Thanks!

No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find limh0sin(ha)h without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...