Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses

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.

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

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (2)
As of 2021-09-22 02:43 GMT
Find Nodes?
    Voting Booth?

    No recent polls found