http://www.perlmonks.org?node_id=227951


in reply to Re: An informal introduction to O(N) notation
in thread An informal introduction to O(N) notation

Your bubble sort examples for O(n) and O(n log n) are the same (the first needs to be un-optimized). Also, I believe the optimized bubble sort is O(n2/2), not O(n log n).

For your second suggestion, loops that can break out early are still O(n) in the worst case, as no guarantee can be made that all other elements will not be considered before the target element.