Sunday 27 October 2013

How to prove $T(n) = Tleft(frac n4right) + Tleft(frac{3n}4right) + n$ is $mathcal O(nlog n)$ using induction?

How would you go about proving the recursion
$$T(n) = T\left(\frac n4\right) + T\left(\frac{3n}4\right) + n$$is $\mathcal O(n\log n)$ using induction?



Thanks!

No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

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