Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail
NNTP-Posting-Date: Sun, 04 Dec 2011 18:14:58 -0600
Date: Sun, 04 Dec 2011 16:14:50 -0800
From: Patricia Shanahan <pats@acm.org>
User-Agent: Mozilla/5.0 (Windows NT 5.2; WOW64; rv:8.0) Gecko/20111105 Thunderbird/8.0
MIME-Version: 1.0
Newsgroups: comp.lang.java.programmer
Subject: Re: Verifying a list is alphabetized
References: <722147ec-ab43-4d7c-8b41-32f8705ee7db@i8g2000vbh.googlegroups.com> <jb5k7n$g4u$1@dont-email.me> <4ed9732b$0$294$14726298@news.sunsite.dk> <jbd5k5$86c$1@dont-email.me> <b5sld7ltif6oi2tke3q2fkr5vnr2cc6nkc@4ax.com> <jbfpru$ksi$2@localhost.localdomain> <WPidnXX0kcoMSEbTnZ2dnUVZ_q6dnZ2d@earthlink.com> <ZrRCq.5933$cN1.371@newsfe12.iad> <jY6dnVhvedWQnkHTnZ2dnUVZ_r2dnZ2d@earthlink.com> <jbh1hf$m6j$1@dont-email.me>
In-Reply-To: <jbh1hf$m6j$1@dont-email.me>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <JOGdnZ4NAKmfkEHTnZ2dnUVZ_rednZ2d@earthlink.com>
Lines: 30
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 70.230.194.31
X-Trace: sv3-MlUwRN8a9Zs0zRvMWIUnqvzcF5pQBFzC7yd6csF16AL7DpzbVHJ5xCNeSDlelQT3m31At3JWMwUmEDm!cMWDzYdE+MmoY5AEXCQ8qYCiRz5DNxFJD0sf+UuiHyD97nKs6/z4hOqY3ZNC/XtuDLBxKnZylkWq!y2ZaMy6Ip0SZ4MTeShly+PCcit6E1WeaYdpJ2QeYBnbH7Q==
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 2606
Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:10505

On 12/4/2011 3:59 PM, markspace wrote:
> On 12/4/2011 3:32 PM, Patricia Shanahan wrote:
>
>> One practical use of such a data set would be to bring home to algorithm
>> design students and programmers choosing algorithms the difference
>> between "average O(n log(n) time" and "O(n log(n)) time", which by
>> default means a bound on the maximum time across all input sets.
>
>
> I think you're missing a parenthesis in the first formula there.

Correct. Sorry about that.

>
> So let me take a stab at that. "Average O" time means, given a bunch of
> different data, we think that some sort of "average" of them will have
> an upper bound of O, but some might not. And "average" means "average of
> the data we measured," not "the data you're using."

Usually, when it is quoted in Big-O notation it should mean "calculated
average over all data sets". Big-O is not really subject to
experimentation, because it is about limits as size tends to infinity.

>
> Whereas "O" means the upper bound is O, period, regardless of the data.
>

Yup.

Patricia