-3
$\begingroup$

problem $T(n) = 3T(n/4) + n \log n$

$f(n) = n \log n$ and $g(n) = n$

Why is $\Omega(g(n)) = O(n \log n)$? Is it because $\Omega$ means at some $n$ and constant, $\Omega(g(n)) = O(n \log n)$?

$\endgroup$
1
  • $\begingroup$ Why do you think that $\Omega(g(n)) = O(n\log n)$? Some context seems to be missing here. $\endgroup$ May 14 at 11:14
2
$\begingroup$

No. Consider $n^2 \in \Omega(g(n))$, obviously, $n^2\notin O(n\log n)$ and therefore $\Omega(g(n)) \neq O(n \log n)$.

$\endgroup$
1
$\begingroup$

Intuitively: $\Omega(\cdot)$ gives a lower bound, $O(\cdot)$ gives an upper bound. If I tell you $x > 1$, you can't deduce an upper bound for $x$ from it.

$\endgroup$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .