Re: ArrayList BinarySearch vs Contains

Hi Bill,

It seems you are suggesting that the scale of the data can affect whether a
required sorting operation will actually reduce the overall performance of an
algorithm so that it becomes worse than a linear search. Can this be true
even when the data is sorted as it's being entered into the structure?

Since I'm not one for micro-optimization either I'd rather just choose an
algorithm with an average performance of O(lg(n)) if I'm sure that there may
be substantial amounts of data at times and just swallow the performance hit
on those smaller collections. I guess if there is a diametric aspect to the
data then maybe switching between linear and binary algorithms at runtime
might be acceptable. I've never had a project that required this much thought
on search algorithms, however :)

Thanks.

--
Dave Sexton

"Bill Butler" <qwerty@xxxxxxxx> wrote in message
news:_4q5h.358$5P2.166@xxxxxxxxxxx
"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: ArrayList BinarySearch vs Contains
    ... a required sorting operation will actually reduce the overall performance ... of an algorithm so that it becomes worse than a linear search. ... data set that's basically infinite. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Calculating two free axes
    ... You can permuate the coordinates if vn is zero to get ... On paper you solve systems of linear equations easily. ... generate a set of linearly independent vectors huh? ... algorithm to do this while I have. ...
    (comp.graphics.algorithms)
  • 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: Regression analysis -- how-to?
    ... > were it not for the fact that, the last time I asked an algorithm ... Do you want to learn about regression? ... > (linear, quadratic, logarithmic, exponential, power and inverse) and at ... > least two types of linear correlation coefficient (rank and product ...
    (comp.lang.pascal.delphi.misc)
  • Re: System Identification
    ... the sum-of-sines contains N/2 sinusoidals. ... the first step of his algorithm. ... which essentially computes the linear prediction coefficients from the ... needs to use the modified covariance equations, ...
    (comp.dsp)