marius311
02-26-2008, 03:27 AM
I'm an undergrad, preparing to teach a section of undergrads some intro computer science and were up to asymptotic complexity, i.e. Big O notation. I want show them how to prove it, so I went online, and to my surprise, every single resource I found did it WRONG! (I think... thats why I'm here).
Heres the general idea... prove that n is O(n^2). That means show that for some N, there is a c such that n<cn^2. Pretty obvious, but bear with me. Take N=1.The method suggested is divide everything over to one side so you n/n^2<c. Now, multiply the left by n (and since n>N i.e. n>1 you're increasing it) so you have n/n^2 < (n*n)/(n^2) < c. And since (n*n)/(n^2)==1 < c if we pick any c>1, then we also have c>n/n^2 and QED.
But wait! We said multiply the left by n, and since n>1 were increasing it. However glaringly obvious this is, we did not prove it. By not proving this, we've infact assumed n<n*n, or that n/(n^2)<1 (for n>1). I would otherwise have no problem with this simple assumption, except that its exactly what were trying to prove, for the special case c=1. So we've assumed what were trying to prove, and proved it, right? So in lieu of this complicated proof I may as well just say "duh, n is O(n^2)" and it would be just as mathematically sound.
Truth is, I might still show them this, since it seems to be what EVERYONE is doing... maybe ask if anyone in the class sees anything wrong with this. Anyway, in my opinion the best way to show f(x) is O(g(x)) is to show that the limit is of f(x)/g(x) as x->Infinity is constant, likely using l'Hopitals along the way.
Any thoughts?
Heres the general idea... prove that n is O(n^2). That means show that for some N, there is a c such that n<cn^2. Pretty obvious, but bear with me. Take N=1.The method suggested is divide everything over to one side so you n/n^2<c. Now, multiply the left by n (and since n>N i.e. n>1 you're increasing it) so you have n/n^2 < (n*n)/(n^2) < c. And since (n*n)/(n^2)==1 < c if we pick any c>1, then we also have c>n/n^2 and QED.
But wait! We said multiply the left by n, and since n>1 were increasing it. However glaringly obvious this is, we did not prove it. By not proving this, we've infact assumed n<n*n, or that n/(n^2)<1 (for n>1). I would otherwise have no problem with this simple assumption, except that its exactly what were trying to prove, for the special case c=1. So we've assumed what were trying to prove, and proved it, right? So in lieu of this complicated proof I may as well just say "duh, n is O(n^2)" and it would be just as mathematically sound.
Truth is, I might still show them this, since it seems to be what EVERYONE is doing... maybe ask if anyone in the class sees anything wrong with this. Anyway, in my opinion the best way to show f(x) is O(g(x)) is to show that the limit is of f(x)/g(x) as x->Infinity is constant, likely using l'Hopitals along the way.
Any thoughts?