Here is the exercise:
Let $\mathcal F = \{f | f : \mathbb Z^+ \to \mathbb R\}$. For $g \in \mathcal F$, we define the set $O(g)$ as follows:
$$O(g) = \{f \in \mathcal F | \exists a \in \mathbb Z^+ \exists c \in \mathbb R^+ \forall x > a (|f(x)| ≤ c|g(x)|)\}$$
(If $f \in O(g)$, then mathematicians say that “$f$ is big-oh of $g$”.)
(a) Let $f :\mathbb Z^+ \to \mathbb R$ and $g : \mathbb Z^+ \to \mathbb R$ be defined by the formulas $f(x) = 7x+3$ and $g(x) = x^2$. Prove that $f \in O(g)$, but $g \notin O(f)$.
And here is the correct solution:
(a) Let $a = 3$ and $c = 8$. Then for any $x > a = 3$,
$$|f(x)| = |7x+3| = 7x+3 < 7x+x = 8x < 8x^2 = c|g(x)|.$$
This shows that $f \in O(g)$.
Now suppose that $g \in O(f)$. Then we can choose $a \in \mathbb Z^+$ and $c \in \mathbb R^+$ such that $\forall x > a(|g(x)| ≤ c|f(x)|$, or in other words, $\forall x > a$ $(x^2 ≤ c(7x+3))$. Let $x$ be any positive integer larger than both $a$ and $10c$. Multiplying both sides of the inequality $x > 10c$ by $x$, we can conclude that $x^2 > 10cx$. But since $x > a$, we also have $x^2 ≤ c(7x+3) ≤ c(7x +3x) = 10cx$, so we have reached a contradiction. Therefore $g \notin O(f)$.
I'm trying to understand the thought process behind the proof that $g\notin O(f)$. What kind of scratch work and thought process has to happen to come to the conclusion that $x>10c$?
They have as a given that $\forall x>a$ $(x^2\le c(7x+3))$, so to come up with a contradiction, they should try to prove that $x^2> c(7x+3)$, so they know that $x^2\le c(7x+3)\le c(7x+3x)=10cx$, (how did they come up with this?). Now since they have $x^2\le 10cx$, they can get a contradiction by defining $x$ as $x>10c$.
But I just don't understand how I could come up with these on my own. Do you think they first derived $x^2\le 10xc$, or decided that $x>10c$?
OP cross posted this to Reddit. Anyways, I shall answer here again.
Assume that $x^2 = O(7x+3)$. Then there's an M > 0 such that $x^2 \le M(7x+3)$ for all sufficiently large x.
We want a contradiction, by proving that $x^2 > M(7x+3) \; ∀$ sufficiently large x.
The trick is to notice that $M(7x+\color{red}{3}) < \underbrace{M(7x+\color{red}{3x})}_{= 10Mx} \; ∀ x > 1$.
Then suffice to prove that $10Mx < x^2 \; ∀$ sufficiently large x. Since $x > 0$, this is equivalent to proving that $10M < x \; ∀ $ sufficiently large x, which clearly holds because M is a fixed constant. QED.
You didn't savvy to replace the 3 with $\color{red}{3x}$, but you can learn a lesson from this. When estimating polynomials, try to make all the exponents equal, because monomials are much easier to work with. This approach can fail, because it can break the desired inequality, but it's a worthy trick to try. If you are working with a quadratic such as $2x^2+3x+4$, then you could have replaced it with $2x^2+\color{MediumSeaGreen}{3x+4} < \underbrace{2x^2+\color{MediumSeaGreen}{3x^2+4x^2}}_{= 9x^2} \; ∀ x > 1$.