Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer

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
Node Status?
node history
Node Type: note [id://227957]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (5)
As of 2018-03-18 20:28 GMT
Find Nodes?
    Voting Booth?
    When I think of a mole I think of:

    Results (230 votes). Check out past polls.