Beefy Boxes and Bandwidth Generously Provided by pair Networks DiBona
Perl Monk, Perl Meditation
 
PerlMonks  

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

by fruiture (Curate)
on Jan 18, 2003 at 12:24 UTC ( #227957=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

Sorry, but that's nonsense. If you say that searching for an element in an unsorted list becomes O(log n) if you stop searchng after you've found the element, you actually say that every element in a list is located among it's first log(n) elements, (where n is the length of the list) and everybody knows that the elements of a list reside within the whole list, that's their definition. So your assumption would be true if there existed some "a" and some "n" for which logan = n, but there is no such a.

Btw.: O(n) does not mean that you don't stop searching a list after you've found the thing you're looking for, of course you do that, but you must expect that you have to search the whole list if the element you're looking for is the last element or not in the list.

But you _can_ make list search O(log n) by keeping the list sorted and then doing binary search.

--
http://fruiture.de


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

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (13)
As of 2014-04-24 11:44 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (565 votes), past polls