Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

Re: Re: An informal introduction to O(N) notation

by MarkM (Curate)
on Jan 18, 2003 at 11:07 UTC ( #227951=note: print w/ replies, xml ) Need Help??


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.


Comment on Re: Re: An informal introduction to O(N) notation

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://227951]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (11)
As of 2014-09-17 11:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (72 votes), past polls