0
$\begingroup$

I am learning big O notation and the attached image popped up in my textbook. I sort of understand the point they are trying to make in the first set of inequalities, the one equal to $4x^2$, but I an totally lost at the one equal to $3x^2$.

I kind of get that they are making the point that $x^2$ will always be greater than $x$ when $x > 1$, but I don not understand why in the second inequality they are not just subbing the correct power in, and why they are changing it to include equals. (My rational being that when $x > 2$, all $x < x^2$ should suffice, but they give me $2x < x^2$).

Any help would be appreciated, thanks.

$\endgroup$
0
$\begingroup$

The definition of Big-O is as follows: $f(x) \in O(g(x))$ if there exist constants $C, k \in \mathbb{R}^{+}$ such that for all $x > k$, $|f(x)| \leq C * |g(x)|$.

In the first argument, the book is choosing $k = 1$ and $C = 4$ and showing the desired inequality holds. In the second argument, the book is instead choosing $k = 2$ and $C = 3$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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