$$\text{Is }\;2^{log(n^2)} = \Omega (\sqrt{n^3}) \;?$$
If I take $n = 1$, I would get $1 = 1$, and if I'd take $n = 2$, I would get $1.52 = 2.82$.
Is that enough to prove that the statement is wrong?
Asked
Active
Viewed 52 times
0
-
The "big Omega" notation typically indicates something about asymptotic behaviour, i.e. what happens as $n$ gets large. You can't just check a few values of $n$, particularly just a few small values. Perhaps what you might try is writing down a correct definition of what it means when $f = \Omega(g)$, then try to apply that definition with $f(n) = 2^{\log(n^2)}$ and $g(n) = \sqrt{n^3}$. – Xander Henderson Oct 30 '18 at 19:56
1 Answers
0
Absolutely not. Big-O and similar notations are not meant to be seen as equalities. They are statements about the behaviour of functions when an argument approaches a value, usually (as in your case) $\infty$.
The question you initially asks means to find out if there exists a positive constant $c$ and a natural number $n_0$ such that
$$2^{\log(n^2)} \ge c \sqrt{n^3}, \forall n > n_0$$
As the formulation about "$\forall n > n_0$" should make clear, looking at one or two values for $n$ can give you absolutely no confirmation either way.
As a hint, try looking at the limit (which may or may not exist)
$$\lim_{n\to\infty}\frac{2^{\log(n^2)}}{\sqrt{n^3}}$$
Ingix
- 14,494