1
$\begingroup$

Can someone explain the following about big-O from the textbook to me? (I'm trying to catch up after missing classes due to illness.)

Show that $f(x) \in O(x^2)$ where $f(x) = 8x+9$. List the witnesses $C$ and $k$.

From what I have gathered I am looking at/for a distinct point witnessed by $C$/$k$ wherein there is a (lower bound?) point to where one of the functions ($f(x)$ or $g(x)$) is increasing at a faster rate for any given point $\geq C$?

The textbook talks testing/trying out different $C$ witnesses (ex. 1) to where I then solve for $8x+9\leq(1)x^2$ or (ex. 2) and solve for $8x+9\leq(2)x^2$, but I'm not sure where I go from there. If I'm letting $C=1$ then I get:

\begin{gather*} 8x+9\leq(1)x^2\\ 0\leq x^2-8x-9\,. \end{gather*}

Then from here I have tried the quadratic equation resulting in $(8 \pm \sqrt{100})/(2)$ or I saw where $0\leq x^2-8x-9$ could be factored to $(x+1)(x-9)$ so I know $-1$ and $9$ make zeroes on my number line, and I tried plugging in test points where I found everything less than $-1$ or greater than $9$ yields a positive, and everything between $-1$ and $9$ yields a negative, but from this point I am lost.

Can someone explain what I'm supposed to be doing and how to go about it?

$\endgroup$
  • $\begingroup$ Maybe you could try complexity notation? Could you try calculating limit (f(x)/g(x)) instead of square root? $\endgroup$ – Evil Feb 18 '16 at 16:44
  • 2
    $\begingroup$ Questions like this abound on the site. Can someone link a close one/duplicate? $\endgroup$ – Raphael Feb 18 '16 at 19:41
  • $\begingroup$ You need to look at the definition of O. $\endgroup$ – Raphael Feb 18 '16 at 19:42
  • 1
    $\begingroup$ There are various definitions of big-O (they're all equivalent but they often differ in the details). Can you tell us what definition your textbook uses? Most of the definitions use two constants, often called $C$ and $k$ but they often use them to mean different things. WIthout knowing what definition you're using, it doesn't make sense to just talk about $C$ and $k$. $\endgroup$ – David Richerby Feb 18 '16 at 19:42
2
$\begingroup$

I am going to guess what $C$ and $k$ mean in your context:

$f(x) = O(g(x))$ if and only if $\exists C, k \;\; \forall x \ge k \;\; (f(x) \le C|g(x)|)$.

You are asked to find constants $C$ and $k$ and prove that for all $x \ge k$ you have $8x+9 \le C x^2$.

I am going to take $C = 1$ and $k = 9$. We have $x \ge 9$ so $C g(x) = C x^2 = x^2 \ge 9 x = 8x + x \ge 8x + 9 = f(x)$.

$\endgroup$
  • $\begingroup$ Note that you don't need to find the optimal $C,k$ (in any sense). That makes your task much easier. $\endgroup$ – Yuval Filmus Feb 19 '16 at 12:35

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.