I had a question in my final exam in data structures, very confusing question, the following:
Prove by the definition that: $15n^2+7n-6= \Omega (17n^2+5n-10)$.
Let's denote: $f(n) = 15n^2+7n-6, g(n) = 17n^2+5n-10.$
From the begining, when i look at this question i was sure there is a mistake here, and instead of $ \Omega $ it's should be $ \Theta $, so firstly i tried to prove that: $$15n^2+7n-6= \Theta (17n^2+5n-10).$$ And - Successfully, it is came true that: $$15n^2+7n-6= \Theta (17n^2+5n-10).$$
Because by the definition:
$f(n) = \Theta (g(n))$ iff there exists $n_0 \in N, c_1,c_2 \in R,$ Such that for each $n \geqslant n_0$ $f(n)$ is bounded from top by $c_2 \cdot g(n)$ and bounded from bottom by $c_1 \cdot g(n)$, like: $c_1 \cdot g(n) \leqslant f(n) \leqslant c_2 \cdot g(n)$.
And here i have successfully found constants like the requirements of the definition: $c_1 = \frac{1}{2}$, $c_2 = 1$, $n_0 = 3$.
And anybody can test it, for each $n_0 \geqslant 3$ you get that: $$\frac{1}{2} \cdot g(n) \leqslant f(n) \leqslant 1 \cdot g(n).$$
Now, in the question it is explicitly stated that $15n^2+7n-6= \Omega (17n^2+5n-10)$, and just need to prove that, and here i proved that is $15n^2+7n-6= \Theta (17n^2+5n-10)$, So my question: Am i wrong, or missing something?
Thanks for help!!
Let $f(n)$ and $g(n)$ be two real function then, $f(n)=O(g(n))$ is equivalent to
$$\begin{align} \exists~ c\in\mathbb{R}: \lim_{n \to \infty}\frac{f(n)}{g(n)} = c \end{align}$$ where, $c\ge 0$
thus $$\lim_{n \to \infty}\frac{15n^2+7n-6}{17n^2+5n-10} $$ $$\lim_{n \to \infty}\frac{15n^2+7n-6}{17n^2+5n-10}=\frac{15}{17} $$
thus it is true that $f(n)=O(g(n))$
Let f(n) and g(n) be two real function then, $f(n)=Ω(g(n))$ is equivalent to
$$\lim_{n\to \infty }\frac{f(n)}{g(n)}=c$$ where $0<c⩽\infty$ (Here c is greater than zero OR can be $\infty$)