Re: ArrayList BinarySearch vs Contains

"Peter Duniho" <NpOeStPeAdM@xxxxxxxxxxxxxxxx> wrote in message
news:12la6mse5o0gsf6@xxxxxxxxxxxxxxxxxxxxx
<snip>
If you have a sorted array, it's true that the worst case is
O(log(n)).

Everyone is making wonderful points on this topic, but I wanted to
underline a few key points.
As Peter said, a BinarySearch on a sorted ArrayList (or a balanced
Binary tree) will have a Worst case performance of O(log(n)).

Another important point of Big O notation is that it describes
Asymptotic behavior. Thus for sufficiently large n an O(log(n))
algorithm will outperform an O(n) algorithm. The problem is determining
what constitutes "sufficiently large n". For small values of n,
O(log(n)) algorithms often perform WORSE than linear algorithms do to
the additional setup complexity. Of course, for small collections, ANY
search will be fast, so it doesn't really matter.

Bill


.

Relevant Pages

  • Re: fastest sorted list type?
    ... implement IComparable for that class and use the default BinarySearch() ... without passing any sort of comparison to it. ... rather than the exact algorithm). ... I did have a look on google and wiki lists al the sort algorothms nicely, ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: fastest sorted list type?
    ... implement IComparable for that class and use the default BinarySearch() ... You can do the sort however you like (assuming, of course, your comparison follows ... The order of the algorithm is basically the ... And if you choose one implementation over another based on this measurement, you should make sure that a) you have used representative data, and b) that the implementation you choose doesn't have a worst-case time cost that could happen with the data you're using. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: ArrayList BinarySearch vs Contains
    ... algorithm so that it becomes worse than a linear search. ... a BinarySearch on a sorted ArrayList (or a balanced Binary ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: RTFM
    ... > Peter T. Breuer wrote: ... intended transfer function out of a digital algorithm). ... >> redeye is caused by getting a reflection off the back of the eye, ...
    (comp.os.linux.misc)
  • Re: RTFM
    ... > Peter T. Breuer wrote: ... intended transfer function out of a digital algorithm). ... >> redeye is caused by getting a reflection off the back of the eye, ...
    (alt.os.linux)
Loading