Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
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?
[Corion]: A good daystart to everybody!
[Corion]: Just a quick poll - is anybody actively relying on https://perlmonks. pairsite.com/? I plan to retire that URL in favour of moving all our servers onto the same HTTPS certificate for perlmonks.{com, net,org}
[Corion]: Actually bsd_glob '{www.,}perlmonks .{com,net,org}', plus css.perlmonks.org I think
[Corion]: Sad that Let's Encrypt does not allow wildcard certificates, but they could be somewhat of a hassle to verify

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (9)
As of 2017-09-26 07:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    During the recent solar eclipse, I:









    Results (292 votes). Check out past polls.

    Notices?