From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 109fba,baaf5f793d03d420
X-Google-Attributes: gid109fba,public
X-Google-Thread: 103376,97188312486d4578
X-Google-Attributes: gid103376,public
X-Google-Thread: 1014db,6154de2e240de72a
X-Google-Attributes: gid1014db,public
X-Google-Thread: fc89c,97188312486d4578
X-Google-Attributes: gidfc89c,public
From: huang@mnsinc.com (Szu-Wen Huang)
Subject: Re: What's the best language to start with? [was: Re: Should I learn
 C or Pascal?]
Date: 1996/08/11
Message-ID: <4ukshk$qcr@news1.mnsinc.com>#1/1
X-Deja-AN: 173533825
distribution: inet
references: <4uaqqg$203@mulga.cs.mu.OZ.AU>
 <01bb84b4$75304ce0$87ee6fce@timpent.airshields.com>
 <4ubnhr$714@news1.mnsinc.com>
 <01bb8536$892ee260$87ee6fce@timpent.airshields.com>
 <4ud8m5$ka5@news1.mnsinc.com> <320bf503.8426726@nntp.ix.netcom.com>
followup-to: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada
organization: Monumental Network Systems
newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada
Date: 1996-08-11T00:00:00+00:00
List-Id: <comp.lang.ada>


Mike Rubenstein (miker3@ix.netcom.com) wrote:
: huang@mnsinc.com (Szu-Wen Huang) wrote:
[snip]
: > The important thing, however, is that I remember that O(n^2) is bad
: > for a sorting algorithm, and O(n lg n) is pretty good.

: But that is not always true.

Of course not, that's why we study best case, average case, and
worst case performances of both time and space of each algorithm.

: A number of years ago I developed a program that had to do a large
: number of sorts with the following characteristics:
[snip]
: Care to try this with quicksort?  or heapsort?  A good old O(n^2)
: insertion sort works quite nicely.

Which is why we examine what causes best- and worst-case behaviors
of each algorithm.  Without assumption on the inputs (and that is
frequently the case), the general knowledge that "quicksort is
better than insertion sort" holds valid.  With additional information
(such as your mostly partially sorted data), what we know about the
best case of insertion sort *and* what we know about how quicksort
performs on sorted input leads us to the correct solution.  In fact,
the general knowledge that many practical quicksort algorithms
switch to insertion sort when partitions are small is already a
most obvious hint to help arrive at the proper solution.

All this to say, assembly language still isn't necessary to understand
algorithms.