Considering the following recursive algorithm: $ T(n)= T(\frac{n}{2})+c_1(\frac {n}{2})^2+c_2n$. I was able to prove that this algorithm is $O(n^2 logn)$ I was trying to understand whether it is a tight bound or not, yet I was unable to prove that $ T(n)\in \Omega(n^2logn)$ Is it possible or maybe the algorithm's lower bound is $n^2$ ? Any assistance would help a lot as I am trying to crack this for a while now.
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
Your recurrence can be written as: $ T(n) = T(n/2) + f(n) $, where $f(n) \in \Theta(n^2)$.
Then, by case 3 of the Master theorem, you have $T(n)=\Theta(n^2)$. This means that you won't be able to prove a lower bound of $\Omega(n^2 \log n)$.
$\begingroup$
$\endgroup$
It's possible that, describe your recurrence as summation:
$$T(n)=T(1)+\sum_{i=0}^{\log n}c_1\left(\frac{n}{2}\right)^2\times\left(\frac{1}{2^i}\right)+ \sum_{i=0}^{\log n}c_2\left(\frac{n}{2^i}\right)$$ $$=\hspace{4pt}T(1)+\sum_{i=0}^{\log n}c_1\left(\frac{n^2}{2^{2+i}}\right)+ \sum_{i=0}^{\log n}c_2\left(\frac{n}{2^i}\right)$$
$$=\hspace{4pt}T(1)+c_1n^2\sum_{i=0}^{\log n}\left(\frac{1}{2^{2+i}}\right)+ c_2n\sum_{i=0}^{\log n}c_2\left(\frac{1}{2^i}\right)=\Theta(n^2).$$
$\begingroup$
$\endgroup$
Your “algorithm” runs in O(log n) time. The function that it calculates is O(n^2).
