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

Results 1 to 6 of 6

- Oct 26th 2008, 01:01 PM #1

- Joined
- Oct 2008
- Posts
- 5

- Oct 26th 2008, 01:14 PM #2

- Joined
- Oct 2008
- Posts
- 51

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 such that

*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

Hope this helps,

- Oct 26th 2008, 01:14 PM #3

- Joined
- Oct 2008
- Posts
- 5

- Oct 26th 2008, 01:27 PM #4

- Joined
- Oct 2008
- Posts
- 51

- Oct 26th 2008, 01:31 PM #5

- Oct 26th 2008, 02:03 PM #6

- Joined
- Oct 2008
- Posts
- 5

Click on a term to search for related topics.