0
$\begingroup$

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.

$\endgroup$

3 Answers 3

1
$\begingroup$

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)$.

$\endgroup$
0
$\begingroup$

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).$$

$\endgroup$
-1
$\begingroup$

Your “algorithm” runs in O(log n) time. The function that it calculates is O(n^2).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.