0

I Expanded (n+1)^5: (n^5+5n^4+10n^3+10n^2+5n+1)/4n^2

simplified and ordered them to be:

n^3/4 + 5n^2/4 + 1/4n^2 + 10n/4 + 5/4n + 10/4

I found if i plug in 6 for testing it satisfies the two first:

  • n^5/4n^2=216/4
  • 5n^4/4n^2=180/4

but for the rest it isn't meeting the rules based on the big o complexity scale. also from 5n^4/4n^2 i don't know where to move from there, in terms of ordering them.

so this is correct as is: n^3/4 + 5n^2/4 + 1/4n^2 + 10n/4 + 5/4n + 10/4.

I then plug in 6 should i not plug in is and get:

216/4>>180/4>>1/44>>60/4>>5/24>>5/2.

then write this fn=O(n^3) for the answer and that's it?

Shanna Chambers
  • 53
  • 7

2 Answers2

1

Hint:

  1. using your high-school algebra skills, turn (n^5+5n^4+10n^3+10n^2+5n+1)/4n^2 into a simple polynomial

  2. using your high-school algebra skills, identify the term in the polynomial which grows fastest as n tends to infinity (i.e. "gets big")

  3. if you can't do step 2 from your math knowledge, draw graphs for each term (on the same sheet of graph paper) ... or write the numbers in tabular form, for increasing values of n.

You are not trying to solve this equation for n. That's not the point.

The point of complexity analysis is to understand how the cost function grows as n gets large. The goal (informally) is to figure out what the function is proportional to. Graphs are one (informal) way to do this.

The answer ... when you work it out ... will be something like O(n^p). Just one term. Based on your question / comments, you don't seem to understand what it is that you are trying to work out here.

I suggest you also go back to your lecture notes or text book to look up the definition of big O complexity. Or read these:

(You can also do it in a mathematically rigorous way; i.e. with an inductive proof and the formal definition of big O notation. But unless you are doing this as part of a University-level Math course, they probably don't expect that level of rigor.)

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
  • simplified and ordered them to be: n^3/4 + 5n^2/4 + 1/4n^2 + 10n/4 + 5/4n + 10/4 – Shanna Chambers Sep 17 '17 at 01:45
  • Now do step 2 / 3 – Stephen C Sep 17 '17 at 01:49
  • I have already ordered them when i plug in 6 which satisfies the condition. it isnt meeting the rules when i reach the third term. can i do something like this: n^3/4 + 5n^2/4 + 10n/4 + 10/4 + 5/4n + 1/4n^2 – Shanna Chambers Sep 17 '17 at 01:51
  • Did you read this? *"You are not trying to solve this equation for n. That's not the point."* The formula is NOT a condition that can be "satisfied". Please re-read my answer, and try to understand what you *should be* doing. – Stephen C Sep 17 '17 at 01:52
  • can i do something like this: n^3/4 + 5n^2/4 + 10n/4 + 10/4 + 5/4n + 1/4n^2. It seems correct if i do this but i don't know if this is accurate in terms of Big O notation. – Shanna Chambers Sep 17 '17 at 01:55
  • I am not understanding what your answer is saying. i am utterly lost and confused at this point. Help!! – Shanna Chambers Sep 17 '17 at 02:00
  • Go back to your lecture notes / textbook. Read the definition of what big O complexity means. – Stephen C Sep 17 '17 at 02:00
  • i just need help solving this one and then its smooth sailing that's how i learn by someone doing something similar then i can see what is done and understand what to do. – Shanna Chambers Sep 17 '17 at 02:02
  • I disagree with your approach. You **won't** understand (properly) by looking at simple examples. – Stephen C Sep 17 '17 at 02:05
  • i know this will be my final answer: fn=O(n^3)∀n≥6 but i don't know if i can leave what is mentioned above as is. – Shanna Chambers Sep 17 '17 at 02:06
  • 1
    Strictly that's not correct. The answer is `fn=O(n^3)`. The `∀n≥6` qualification is not necessary. But you would *understand* that if you *understood* what Big O notation *actually means*. – Stephen C Sep 17 '17 at 02:09
  • that's how my lecturer thought us to represent it. I have read alot on the topic and saw it is writtent that way, but thats how he represent it to us and wants us to do it. – Shanna Chambers Sep 17 '17 at 02:11
  • oh ok well so this is correct as is: n^3/4 + 5n^2/4 + 1/4n^2 + 10n/4 + 5/4n + 10/4. I then plug in 6 should i not plug in is and get 216/4>>180/4>>1/44>>60/4>>5/24>>5/2. then write this fn=O(n^3) for the answer and that's it? – Shanna Chambers Sep 17 '17 at 02:17
  • Yes. That is the answer. (You need to understand *why* it is the answer ... IMO. Read the links in my Answer.) – Stephen C Sep 17 '17 at 02:22
  • i know its assumptions i read it awhile ago, but 216/4>>180/4>>1/44>>60/4>>5/24>>5/2. doesn't look true to me – Shanna Chambers Sep 17 '17 at 02:24
  • Try it for larger N (and smaller too). You can't judge these things based on a single data-point! – Stephen C Sep 17 '17 at 02:55
  • well, lecturer suppose to explain the question to us. – Shanna Chambers Sep 19 '17 at 00:03
1

The numerator is a polynomial of degree 5, the denominator is a polynomial of degree 2.

In complexity this leads straight to the answer of 5 - 2 = 3, or in other words n^3

Use polynomial long division for instance to convince yourself of this. But otherwise know that the degrees can be immediately subtracted in this fashion when it comes to polynomial complexity.

If you were to plot the graph of your initial polynomial fraction, and 'widened' the view to see more and more positive n values, the plot would look more and more like a plot of n^3 ...

Lamar Latrell
  • 1,669
  • 13
  • 28