Is it possible to prove that this algorithm is big Omega $n^2logn$ time complexity? 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.
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)$.