Re: A question: Is 200,000 element array worth sorting and search?

On 5 May, 01:26, Keith Thompson <ks...@[EMAIL PROTECTED]
> wrote:
> mike-yue <needpass...@[EMAIL PROTECTED]
> writes:

....

> > I think it is useless for 99% programmer jobs, unfortunately it's
> > always been asked. Once a interviewer asked me to explain the
> > algorithmic complexity of quick sort!
>
> And this was a problem?  That's certainly something I'd expect any
> good programmer to know.  If you're going to be writing code that does
> sorting and searching, and you don't know this stuff, there's an
> excellent chance your code is going to be unacceptable slow.
>
> (Quicksort is O(N log N) best case and average case; a straightforward
> implementation is O(N**2) worst case, but it can be made O(N log N)
> with a little tweaking.)

It's not difficult to /state/ the complexity of quicksort (assuming
one remembers it) but it is another thing to /explain/ it.

--