Big-O Notation, and reading comprehension

[Goldenwind]

Homework Statement

These are some problems I need to solve. Do not solve them for me. I ask two things from you:

1) Explain what the question is asking from me, as I'm a little unclear on this.
2) Using a completely unrelated example, or whichever not-doing-it-for-me method you wish, give a hint as to how I might actually be able to do these.

Question 1: Find the least integer n such that f(x) is O(x^n) for each of these functions.
a) f(x) = 2x^2 + x^3 * log(x)
b) f(x) = 3x^5 + (log(x))^4
c) f(x) = (x^4 + x^2 + 1) / (x^4 + 1)
d) f(x) = (x^3 + 5log(x)) / (x^4 + 1)Question 2: Give a big-O estimate for each of these functions. For the function g in your estimate that f(x) is O(g(x)), use a simple function g of the smallest order.
a) nlog(n^2 + 1) + n^2 * log(n)
b) (nlog(n) + 1)^2 + (log(n) + 1)(n^2 + 1)
c) n^(2^n) + n^(n^2)

Homework Equations

1, logn, n, nlogn, n^2, 2^n and n! are the "often used" terms.

The Attempt at a Solution

I read the textbook. My problem might be as simple as not understanding what they're asking, but totally knowing how to do it, or maybe I don't understand it anyway... I can't really gauge that until I figure out what they want :P

 

[tiny-tim]

Hi Goldenwind!

x^7, for example, is O(x^8) and O(x^9), but not O(x^7) or O(x^6) or …

So 8 is the least integer for which x^7 is O(x^n).

(warning! warning! I may have got this completely wrong, because I can't remember the definition of O() off-hand - but I hope you see what I'm getting at. )

 

[HallsofIvy]

Slightly wrong, tiny-tim, according to what I know as the "usual definition". "f= O(g)" means that the limit (as x goes to infinity) of f/g exists and is non-zero. Neither x⁷= O(x⁸) nor x⁷ x⁹) is correct but x⁷= O(x⁷).

You are thinking of "small o"- f= o(g) means that the limit of f/g is 0. It is true that x⁷= o(x⁸ and x⁷= o(x⁹) but x⁷ is not o(x⁷).

Those are "usual definitions". Having typed all that, I noticed that the problem said "the smallest n such that". The "O" definition above clearly gives at most a single n for each function- it may well be true that the problem is talking about "o", not "O". And perhaps Goldenwind typed "O" rather than "o" without realizing it. Goldenwind, can you check on that?

For example, with problem (a), f(x)= x²+ x³ln(x). Since 3> 2, x²+ x³ would be O(x³) because (x²+ x³)/x³= 1/x+ 1 which goes to 1 as x goes to infinity. It would be o(x⁴ or any higher power of n, because (x²+ x³)/xⁿ= 1/x^n-2+ 1/x^n-1 which goes to 0 for any n> 3.

However, since ln(x) goes to infinity, but ln(x)/x goes to 0, x²+ x³ln(x) is not O(xⁿ) for any integer n but is o(xⁿ for any n higher than 3.

 

[Goldenwind]

Nope, 'tis Big-O =/

Also, haven't a clue what you mean with limits :P
All I know is Big-O means that f(x) <= C*g(x) when x > k, for some C,k.

/boggle XD

 

[e(ho0n3]

That definition means that f(x) = O(g(x)). Now, for f(x) = 2x^2 + x^3 * log(x), you want to find the least n such that 2x^2 + x^3 * log(x) <= Cx^n when x > k for some C and k. Can you find the least n now?

 

[Goldenwind]

I now understand what is being asked of me.
When n = 3, Cx^3 grows faster than 2x^2... and log(x) will dampen the effectiveness of x^3, so technically x^3 > x^3*log(x)...

...so for that one, n=3 would be the smallest?
Am I on the right track?

 

[Goldenwind]

Actually, would x^2 grow faster than x^3*log(x)?
'cause x^3 is bigger than x^2, but log(x) is a serious dampener...

Edit: Got it now! ^^;
Thanks :)

I know how to solve all of the first question now.
And I also get what the second question is asking.

 

[Goldenwind]

In the first question, we were given x^n, and told to solve for n.
In the second question, we aren't given any function, but are just told to find the Big-O.

How do I know which function g(x) is, to compare to f(x)?

 

[e(ho0n3]

When n = 3, Cx^3 grows faster than 2x^2... and log(x) will dampen the effectiveness of x^3, so technically x^3 > x^3*log(x)...

No. log(x) doesn't "dampen the effectiveness" of x³. Your intuition is wrong. Pick a large value of x, say 1000, and tell me which one is greater: x³ or x³log x.

Actually, would x^2 grow faster than x^3*log(x)?
'cause x^3 is bigger than x^2, but log(x) is a serious dampener...

Again, your intuition is wrong. Let x = 1000 and compare the two.

In the first question, we were given x^n, and told to solve for n.
In the second question, we aren't given any function, but are just told to find the Big-O.

How do I know which function g(x) is, to compare to f(x)?

You're told to find a simple function g (e.g. xⁿ) of the smallest order. Let's look at the first one: nlog(n² + 1) + n² * log(n). First start by determining which of the two terms grows faster.