Big O Notation

[mooeypoo]

Hi guys!

 

So, yesterday was my first day as a grad student, and my first grad-level class. Yay. I'm also the only one in class that is not a computer-science major in undergrad, but rather a physics major. The teacher said that will help me in this class since it's more a 'math-oriented' course, but ... I'm... not so sure.

 

I have a feeling that the approaches of how "proof" works or how to consider a proof varies drastically between what I am used to from Physics and what I'm supposed to follow here in compsci class. I might be wrong, though, but either I didn't manage to phrase my questions correctly in class or I completely misunderstood the process on the board.

 

So.. here I am, asking you guys!

 

We were talking about the Big O Notation and its proof.

I understand the goal of big-o-notation in terms of compsci, as a method of checking the complexity of an algorithm and factoring in how much time it would take to solve, etc. It makes sense, I understand it, and I see its use.

 

What I don't get is the professor's example of "how to prove it", and it seemed to me that the proof was more based on initial assumptions and "leading to the answer we want" rather than actual proof. Then again, I always had that problem with mathematic's "Let's assume X=whatever, and prove it" approach. eh.

 

in class, the professor used this proof, here: http://en.wikipedia.org/wiki/Big_O_notation#Example

(He used a slightly different f(x) but the same idea)

 

We already pick the "highest growth" factor and then went step-by-step to make it easy for us to solve, ti seems. This whole "bigger than" methodology where we seem to change the variables arbitrarily just to make it comfortable for us to solve might be "rigidly true" but it's .. also.. leading, isn't it? how can you have a proof that's on its face a LEADING process. You basically decided what you want to have, and now you're leading towards the solution you invisioned.

(Example, x^4 is bigger than x^2, but so is x^3, and yet we picked x^4 purposefully to make it "easier" to solve...)

 

In class, I asked that if our goal is to simply find the factors of the variable that is "highest growth" why aren't we working with limits. I didn't quite understand the answer the professor gave me, hoenstly, but when I researched online, I found this:

http://en.wikipedia.org/wiki/Big_O_notation#Formal_definition

Which indeed goes by limits, and.. makes more sense to me.

 

 

 

So.. I guess my question is this -- am I wrong to say that the example (whic my professor used as "proof") is not proof, or is, at least, a proof-after-you-already-know-what-to-look-for?

 

And to illustrate my point, this might be extremely easy when we deal with polynomials, but that "proof" becomes a lot harder if the algorithm has a mix of exponential factors, not to mention if it is a partial derivative or "worse" a mix of those. If that happens, you no longer have an "obvious" strongest factor to "aim towards" in that example of 'bigger than / smaller than' and when that is the case, you can't solve it. You HAVE to revert to limits.

 

And if a proof only works in certain cases, it's not a proof.

 

 

..... is it???

 

 

I'm confused. I hope I'm making sense at all in expressing where my confusion lies... am I just expecting "physics'y" methods in a place where I should just be satisfied with "engineering" questions? That sounds a bit insulting to engineering if that's true... but I don't know, and no one in class understood much to help me.

 

~mooey

[timo]

Yay. I'm also the only one in class that is not a computer-science major in undergrad, but rather a physics major.

My condolences. Until a few weeks ago I thought physicists were slightly socially awkward. Then I picked up a new job and met the computer scientists.

 

I don't quite understand your issues with the proof given on Wikipedia (assuming you are referring to the four lines of inequality on the section you linked to). It is absolutely common that in a mathematical proof you make steps that help you (e.g. x^4 >= x^2 for all x>=1) instead of steps that don't help you (x^3 >= x^2 for x>=1). You need to convince yourself (and the juror of your proof) that the steps are correct. But a proof for a statement is not necessarily unique. And there is nothing wrong with trying to prove a statement that you made prior to the proof.

 

EDIT: Perhaps I should at the following for clarification: The proof does not prove that the function is not O(x^3).

Edited September 6, 2012 by timo

[md65536]

So.. I guess my question is this -- am I wrong to say that the example (whic my professor used as "proof") is not proof, or is, at least, a proof-after-you-already-know-what-to-look-for?

 

Big-O proofs are proofs. Doing a proof doesn't always give you an answer you're looking for, so often some other method would be used to arrive at a guess, and the proof would be used to show the guess is correct. Isn't it the same with maths proofs?

 

Big-O provides an upper limit, so anything in O(x^2) should also be in O(x^3), right? So you don't need to know what to look for to arrive at a correct proof. But proving something is in O(x^2) is more useful than proving it's in O(x^3).

 

 

[studiot]

Gosh, how does anybody prove a notation?

 

Sure not?

 

Incidentally I don't think I have ever seen a maths proof that runs "assume X to be true and because......Y, Z are true or defined, X must be true"

 

Normally this works for disproof ie "Assume X is true and show a contradiction ... Therefore X is false"

 

Proof by Induction works on the basis of "demonstrating that X+1 must be true if X is true"

Edited September 6, 2012 by studiot

[mooeypoo]

My condolences. Until a few weeks ago I thought physicists were slightly socially awkward. Then I picked up a new job and met the computer scientists.

 

I don't quite understand your issues with the proof given on Wikipedia (assuming you are referring to the four lines of inequality on the section you linked to). It is absolutely common that in a mathematical proof you make steps that help you (e.g. x^4 >= x^2 for all x>=1) instead of steps that don't help you (x^3 >= x^2 for x>=1). You need to convince yourself (and the juror of your proof) that the steps are correct. But a proof for a statement is not necessarily unique. And there is nothing wrong with trying to prove a statement that you made prior to the proof.

 

EDIT: Perhaps I should at the following for clarification: The proof does not prove that the function is not O(x^3).

I think my problem is that I'm trying to generalize the case. If I see "PROOF" I want to make sure that I can do it on any given scenario to solve the issue.

 

The inequality steps might work with polynomials, but what do you do when you have a mix of exponentials, or some mix of exponentials inside roots, etc?

 

This inequality process seems to rely on your INSTINCT to choose the proper "g(x)" and then prove it. That might be fine when the f(x) given is simple, but what do you do when your instincts aren't sufficient?

 

If I plan to be a computer science person that does physics simulations (which is more or less what I want to do), then I should take into account that this O-notation will come most handy when the algorithm in question is the most complex. For instance, in a class a while back we were doing some calculations involving Kepler's equations and adding perturbations to it. We wanted to calculate the location of some planet at some particular date relative to another planet. This may be doable in small increments, but it gets rather complicated if you want to calculate this for 10,000 years from now. The equation also may include a partial derivative, which is not uncommon in physics.

 

No matter how intuitive you are, I don't see anyone just doing an inequality as a form of proof for the O-notation when such a complicated algorithm is involved. You don't necessarily always have the luxury of "guesstimating" correctly what to guess towards in your inequality proof.

 

Do you see what I mean?

 

~mooey

 

 

P.S On *top* of the above problem, I also have a personal conceptual issue with the idea that I have to firt reach a conclusion and then try to prove the conclusion mathematically as part of a proof. I am fully aware this is a personal problem with the way mathematics works, and I know that there are many cases where math does just that. I still get annoyed with this, though... can't help it.

~mooey

[timo]

Not sure how to formulate a coherent text. There is a lot that could be said, but I'd prefer you put it into context yourself, so I'll use bullet points.

• If I understood you correctly you now agree that what your professor showed you is a proper proof. This should imply that you believe the statement. This is all a proof is for.
  
• You do not have to like the proof. You may prefer other forms to prove the same statement for whatever reason. You are, in principle, entitled to your own style preferences (though in practice the necessity for interaction with colleagues limits this).
  
• The WP proof could be straighforwardly modified to show that the function is O(x^13). Correctness of a statement does not imply usefulness.
  
• Needing to proof a particular statement/assumption occurs frequently. For example, a Monte Carlo algorithm properly scans the possible events if it is ergodic and obeys detailed balance (no need to understand what that means). So if I devise an MC algorithm, I have quite an interest to prove these two assumed properties.
  
• I recommend for talented young scientists to explore their own ideas. But don't let it get into your way.
  
• In practice, the whole big-O thing is simple handwaving stuff. The reason your prof deals with it with some rigor is because otherwise some smart-ass would try to correct him. Didn't really work out, since now he has a smart-ass trying to generalize him .
  
• Computational Science/Physics can apparently mean some variety of things. I've worked in the field of computational physics (with emphasis on physics) for the last four years. I have not met a single computer scientist, there (those were the times ... ).
  

Edited September 6, 2012 by timo

[mooeypoo]

I agree the proof proves the specific type of argument presented. I don't quite see it generalized, which, as far as I'm concerned, is a problem if it's supposed to check the complexity of algorithms in general.

 

Then again, I think I see what you mean.. and... I'll try to be less of a smartass, maybe if I see more examples of how it's supposed to be actually dealt with I will understand whether or not it could be generalized... or.. not...

 

Thanks

 

~mooey