Sunday, January 5, 2020

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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...