Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot

Re: An informal introduction to O(N) notation

by BUU (Prior)
on Jan 18, 2003 at 05:26 UTC ( #227926=note: print w/replies, xml ) Need Help??

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

O(N2) says that the algorithm's performance is proportional to the square of the data set size. This happens when the algorithm processes each element of a set, and that processing requires another pass through the set. The infamous Bubble Sort is O(N2).
Shouldn't bubble sort be O(NN) as you might have to process the entire thing once for each element, if it was sorted backwords for example?
  • Comment on Re: An informal introduction to O(N) notation

Replies are listed 'Best First'.
Re: Re: An informal introduction to O(N) notation
by jryan (Vicar) on Jan 18, 2003 at 09:38 UTC
    So, thats one sort for each element in an n sized list... and if each sort is O(n) for one member, then n*n = ?

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://227926]
[Corion]: Oooh - I had another devious idea - "Host C" - a C language where every struct is 4K in size. This makes memory and disk access incredibly fast ;)
[Corion]: (because everything is aligned to a memory page and all pages can be read+written directly from disk without buffering)

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (6)
As of 2017-04-25 08:55 GMT
Find Nodes?
    Voting Booth?
    I'm a fool:

    Results (449 votes). Check out past polls.