Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re: An informal introduction to O(N) notation

by FoxtrotUniform (Prior)
on Feb 08, 2003 at 23:26 UTC ( #233791=note: print w/ replies, xml ) Need Help??


in reply to An informal introduction to O(N) notation

    The infamous Bubble Sort is O(N2).

So is quicksort, in the worst case. :-) Mergesort and heapsort are both O(N log N) in the worst case.

Most of the time, there's no difference in asymptotic order between the average- and worst-case inputs, but every once in a while, something (like quicksort) comes along and bites you on the ass on certain inputs. Quicksort expects its input to be mostly random; ordered input will mess it up. (Think about building a binary tree from ordered input: you'll get a linear list, which is O(N) nodes deep, not a nice bushy tree, which would be O(log N) nodes deep.) Something to think about when building divide and conquer algorithms.

--
F o x t r o t U n i f o r m
Found a typo in this node? /msg me
The hell with paco, vote for Erudil!


Comment on 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://233791]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (15)
As of 2015-07-31 12:15 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (277 votes), past polls