Big-O Notation, and reading comprehension

You should be able to see right away that n2 * log(n) grows faster than nlog(n2 + 1). So, you need to compare this to xn for some n.In summary, the conversation discusses two questions related to finding the least integer n such that f(x) is O(x^n) for a given function and determining a big-O estimate for a set of functions. The first question asks for an explanation of the problem and a hint on how to solve it, while the second question asks for a big-O estimate and to compare it with a simple function of the smallest order. The conversation also includes a discussion on the difference between "O" and "o" notation and the role of limits in determining the least
  • #1
Goldenwind
146
0

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
 
Last edited:
Physics news on Phys.org
  • #2
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. :redface:)
 
  • #3
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 x7= O(x8) nor x7 x9) is correct but x7= O(x7).

You are thinking of "small o"- f= o(g) means that the limit of f/g is 0. It is true that x7= o(x8 and x7= o(x9) but x7 is not o(x7).

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)= x2+ x3ln(x). Since 3> 2, x2+ x3 would be O(x3) because (x2+ x3)/x3= 1/x+ 1 which goes to 1 as x goes to infinity. It would be o(x4 or any higher power of n, because (x2+ x3)/xn= 1/xn-2+ 1/xn-1 which goes to 0 for any n> 3.

However, since ln(x) goes to infinity, but ln(x)/x goes to 0, x2+ x3ln(x) is not O(xn) for any integer n but is o(xn for any n higher than 3.
 
  • #4
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
 
  • #5
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?
 
  • #6
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?
 
  • #7
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.
 
Last edited:
  • #8
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)?
 
  • #9
Goldenwind said:
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 x3. Your intuition is wrong. Pick a large value of x, say 1000, and tell me which one is greater: x3 or x3log x.

Goldenwind said:
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.

Goldenwind said:
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. xn) of the smallest order. Let's look at the first one: nlog(n2 + 1) + n2 * log(n). First start by determining which of the two terms grows faster.
 

What is Big-O Notation?

Big-O Notation is a way of expressing the time complexity of an algorithm. It tells us how the algorithm's performance changes as the size of the input grows. In simpler terms, it helps us understand how efficient an algorithm is.

Why is Big-O Notation important?

Big-O Notation is important because it allows us to compare the efficiency of different algorithms. By understanding the time complexity of an algorithm, we can make informed decisions about which algorithm to use for a particular problem. It also helps us identify potential performance issues in our code.

How is Big-O Notation calculated?

Big-O Notation is calculated by looking at the number of operations an algorithm performs with respect to the size of the input. It focuses on the worst-case scenario, meaning that it considers the maximum number of operations an algorithm might perform for a given input size.

What are the common complexities in Big-O Notation?

The most common complexities in Big-O Notation are O(1), O(log n), O(n), O(n log n), O(n^2), and O(2^n). These complexities represent algorithms that have constant, logarithmic, linear, linearithmic, quadratic, and exponential time complexity, respectively.

Can Big-O Notation be used for both time and space complexity?

Yes, Big-O Notation can be used for both time and space complexity. While it is most commonly used to measure time complexity, it can also be used to measure the space complexity of an algorithm. The same principles apply, but instead of looking at the number of operations, we look at the amount of memory an algorithm uses with respect to the input size.

Similar threads

  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
564
  • Calculus and Beyond Homework Help
Replies
1
Views
241
  • Calculus and Beyond Homework Help
Replies
10
Views
972
  • Calculus and Beyond Homework Help
Replies
1
Views
496
  • Calculus and Beyond Homework Help
Replies
16
Views
553
  • Calculus and Beyond Homework Help
Replies
3
Views
253
  • Calculus and Beyond Homework Help
Replies
1
Views
949
  • Calculus and Beyond Homework Help
Replies
3
Views
542
  • Calculus and Beyond Homework Help
Replies
7
Views
264
Back
Top