Re: ArrayList BinarySearch vs Contains

Hi Jon,

I must admit that my incomplete understanding of the O notation wasn't
based
solely on wikipedia. I've always believed it to represent "worst-case",
not
average, for many years now. It's the math that makes it confusing, yet I
thought I had it right :p

I think that when the two are significantly different, it's best to
give both. For instance, QuickSort has an average O(n log n)
complexity, but its worst case is O(n^2) IIRC.

That's a good idea to cover all bases.

Then the difficulty comes in comparing two algorithms that have asymmetric
average to worst case ratios. How can the algorithms be compared when they
don't have any common denominator?

What I mean is that it's much easier to chose an algorithm based on either
average time or worst-case time but it's hard for me to compare both, so which
aspect has more relevance? Of course, I'd agree that it's better to have all
the information on hand when making the decision (even though ignorance is
bliss, as they say ;)

BTW, wikipedia agrees with your math and so does the Array.Sort doc on MSDN,
so it seems you did remember correctly.

"Quicksort"
http://en.wikipedia.org/wiki/QuickSort

(The Quicksort article is particularly interesting with its visual
representations of the sort in action)

"Array.Sort Method"
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/cpref/html/frlrfsystemarrayclasssorttopic.asp

--
Dave Sexton


.

Relevant Pages

  • Re: simple math question
    ... finished high school and before the net was nearly as big. ... computer science, algorithms and math, let alone crypto, should NOT be ... Learn math. ... my interest in cryptography didn't really 'spark' until after college. ...
    (sci.crypt)
  • Re: Wikipedia and me
    ... math people's attempts at slanting that encyclopedia with their own ... First off, like most I came upon the Wikipedia as a useful resource, ... and removing more libelous and hostile remarks. ... people by continually trying to edit the article to make it objective. ...
    (sci.skeptic)
  • Wikipedia and me
    ... math people's attempts at slanting that encyclopedia with their own ... First off, like most I came upon the Wikipedia as a useful resource, ... monitor the math wars, I found a search result showing up on the ... Someone came back, reverted my edits. ...
    (sci.skeptic)
  • Re: Wikipedia and me
    ... math people's attempts at slanting that encyclopedia with their own ... First off, like most I came upon the Wikipedia as a useful resource, ... and removing more libelous and hostile remarks. ... Someone came back, reverted my edits. ...
    (sci.skeptic)
  • Re: algorithmic composition
    ... The best algorithmic composition I've heard comes from Michael Gogins, ... of pure mathematics. ... I'm not a math person. ... you can make very nice fractal images using simple algorithms. ...
    (rec.music.compose)