1. ## Big-O

When it comes to Big-O notation, I draw a blank. I have the question:

Use the definition of "f(X) is O(g(x))" to show that 2x+17 is O(3x)

and i'm just wondering if anyone could help me get started

2. Okay. As for the definition, it informally says: 'f(x) is (or belongs to) O(g(x)) if, for all numbers bigger than some arbitrary number A the growth of g(x) is faster than or as fast as f(x)'s.'

Since the formal definition includes a constant, most authors would simply ask you to prove that 2x + 17 is O(x).

Nevertheless, to conclude your proof all you must do is show some real number $\displaystyle x_0$ such that $\displaystyle 2x + 17 <= 3x, x > x_0$

EDIT: Jhevon correctly pointed out that you need to specify where x is going. As the most common application of Big O is to show assymptotical domation of one funcion over another, I assumed $\displaystyle x \rightarrow \infty$

Hope this helps,

3. Find witnesses C and k such that |f(x)| ≤ C|g(x)| whenever x > k
Use the definition of

$\displaystyle f(X)$ is $\displaystyle O(g(x))$ to show that $\displaystyle 2^x+17$ is $\displaystyle O(3^x)$

I've never truly understood Big-O, so i don't know where to start.

4. Originally Posted by Numbah51
Find witnesses C and k such that |f(x)| ≤ C|g(x)| whenever x > k
Use the definition of

$\displaystyle f(X)$ is $\displaystyle O(g(x))$ to show that $\displaystyle 2^x+17$ is $\displaystyle O(3^x)$

I've never truly understood Big-O, so i don't know where to start.
Notice that even though my answer assumed f and g were linear functions, the process is the same: prove that $\displaystyle 2^x+17 \leq C3^x, x > x_0, C \in \mathbb{R}$.

To get you a better view, putting the formalist aside a little bit, show that 'eventually $\displaystyle 2^x+17$ doesn't grow faster than $\displaystyle 3^x$.

5. Originally Posted by Numbah51
Find witnesses C and k such that |f(x)| ≤ C|g(x)| whenever x > k
Use the definition of

$\displaystyle f(X)$ is $\displaystyle O(g(x))$ to show that $\displaystyle 2^x+17$ is $\displaystyle O(3^x)$

I've never truly understood Big-O, so i don't know where to start.
choose C = 7 and k = 1

6. Thank you guys so much, i understand it now and answered my question. I really appreciate all your help.

,

,

,

,

### use the definition of f(x) is o(g(x)) to show that

Click on a term to search for related topics.