laziness, impatience, and hubris  
PerlMonks 
Re: An informal introduction to O(N) notationby jryan (Vicar) 
on Jan 18, 2003 at 10:04 UTC ( #227946=note: print w/ replies, xml )  Need Help?? 
It should be noted that many algorithm's O time can be reduced. For instance, many O(n^2) algorithms can be reduced to O(n log(n)) by finding a way to cut the inner loop short. A famous example is bubblesort:
O(n) algorithms that involve a search via a loop can sometimes be reduced from O(n) to O(log(n)) by breaking out of the loop once a "result" is found:
Of course, the secret is to know where to apply these optimizations, which is often harder than it seems :)
In Section
Meditations

