Big O Need a hint please

Dr.Peterson said:
A good place to start would be to find the formal definition of Big O. What is it? State it, and then apply it to this question.
Click to expand...
Definition for Big-O

http://prntscr.com/lq3zuq

this is the solution given by someone:

http://prntscr.com/m56f1q

however i do not understand where they got 300n^2 at the right side of the inequality shouldn't it be 300n^3?

what changes are needed in that solution?
 
Last edited:
sita said:
Definition for Big-O

http://prntscr.com/lq3zuq

this is the solution given by someone:

http://prntscr.com/m56f1q

however i do not understand where they got 300n^2 at the right side of the inequality shouldn't it be 300n^3?

what changes are needed in that solution?
Click to expand...
Hi, I do not think that Dr P wanted you to look up the definition, unless you really did not know it. We want to know your definition of it in your own words. That will tell us if you have a good understanding of the definition.

A quick story. I was taking an (advanced) algebra class where our teacher gave us 10 proofs to do. It took me a whole week and many hours to do these proofs and I got 9 of them done. I found the 10th one worked out in a textbook I owned. This 10th proofs was one of the easier ones but I just didn't see it myself. The day the assignment was due I left my work at home. I thought not a big deal since I could easily write up the proofs. Well I was partly right. I easily wrote up the proof for 9 of them but could not remember the proof that I saw in my book. I had to go home to get my work.The moral of the story is that doing the work yourself is very beneficial to you compared to looking at someone else's work. Be touch, play hard and you'll do fine.
 
Jomo said:
Hi, I do not think that Dr P wanted you to look up the definition, unless you really did not know it. We want to know your definition of it in your own words. That will tell us if you have a good understanding of the definition.

A quick story. I was taking an (advanced) algebra class where our teacher gave us 10 proofs to do. It took me a whole week and many hours to do these proofs and I got 9 of them done. I found the 10th one worked out in a textbook I owned. This 10th proofs was one of the easier ones but I just didn't see it myself. The day the assignment was due I left my work at home. I thought not a big deal since I could easily write up the proofs. Well I was partly right. I easily wrote up the proof for 9 of them but could not remember the proof that I saw in my book. I had to go home to get my work.The moral of the story is that doing the work yourself is very beneficial to you compared to looking at someone else's work. Be touch, play hard and you'll do fine.
Click to expand...
This is my understanding of the approach to the definition, please see what i did and tell me if its ok.

image1.jpg
 
sita said:
Definition for Big-O

http://prntscr.com/lq3zuq

this is the solution given by someone:

http://prntscr.com/m56f1q

however i do not understand where they got 300n^2 at the right side of the inequality shouldn't it be 300n^3?

what changes are needed in that solution?
Click to expand...

Yes, there is an obvious copying error there, which you can fix, right? It's your thinking that is important, not someone else's. Make whatever corrections you see needed, as you work through it, step by step, check why each statement is true (or not). In a way, that can help you to think carefully about the proof, more than just copying a fully correct answer.

But the error is the 300n^2 at start of the right side of the first inequality, which is copied into the left side of the last two inequalities, right?

Now, you haven't quite stated everything needed in the definition; what are c and n0? And how do you know that n^3 > n^2 log_2(n)?
 
Dr.Peterson said:
Yes, there is an obvious copying error there, which you can fix, right? It's your thinking that is important, not someone else's. Make whatever corrections you see needed, as you work through it, step by step, check why each statement is true (or not). In a way, that can help you to think carefully about the proof, more than just copying a fully correct answer.

But the error is the 300n^2 at start of the right side of the first inequality, which is copied into the left side of the last two inequalities, right?

Now, you haven't quite stated everything needed in the definition; what are c and n0? And how do you know that n^3 > n^2 log_2(n)?
Click to expand...
We prove that the complexity class is O(n^3 ).In accordance with the definition of big-O we need to show, that 'the equation' <= c * n^3 for all n >= n0 and some constant c.

Because n^3 is the bigger power in the entire equation.
 
Dr.Peterson said:
Yes, this is a lot better than the "someone" who did the other. I presume this is your own work. You've done what I asked for after you wrote this.
Click to expand...
Thanks Dr Peterson i will now motivate myself to work based on my brain and suggest what working i have next time. :)
 
Jomo said:
Hi, I do not think that Dr P wanted you to look up the definition, unless you really did not know it. We want to know your definition of it in your own words. That will tell us if you have a good understanding of the definition.
Click to expand...

Actually, I did want Sita to look up the definition, because that is the start of the process (and some people don't know to start there). The next step is to apply it, which is where we see if there is any understanding. But your reminder is a helpful one.

Interestingly, the request was for a hint, which seems not to have been needed. Sometimes the most important "hint" is a reminder to just get started doing something with what you already know.
 
You must log in or register to reply here.
Top