<aside> <img src="https://super.so/icon/dark/alert-triangle.svg" alt="https://super.so/icon/dark/alert-triangle.svg" width="40px" /> These examples were done in Prof. Frid’s class during FQ 2020. If any of these shows up in a homework, let me know immediately.
</aside>
$$ T(n) = 2T\left(\frac n2\right) + O(n) $$
Given the guess is $O(n\log n)$, show that $T(n)$ is actually $O(n\log n)$
$$ T(n) = T\left(\frac n2\right) + O(1) $$
Given the guess is $O(\log n)$, show that $T(n)$ is actually $O(\log n)$
$$ T(n) = T\left(\frac n5\right) + T\left(\frac {7n}{10}\right) + O(n) $$
Given guess is $O(n)$, check if the guess is correct by substitution.
$$ T(n)=4T\left(\frac n2\right) + n $$
Go to next:
