I did check for $O(n^3)$ by $$ T(k) \leq ck^3-k^2 $$for all k<n. It is O(n^3) however checking for O(n^2), can I pick T(k) as $$ T(k) \leq ck^2 - k^{1.5} $$ or something like that. Then we can show that is $O(n^2)$. It is also $Ω(n)$ by $T(k) \le ck$ for all $k < n$.

How do I further improve this using substituion method?



You must log in to answer this question.

Browse other questions tagged .