Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #10505

Re: Verifying a list is alphabetized

Date 2011-12-04 16:14 -0800
From Patricia Shanahan <pats@acm.org>
Newsgroups comp.lang.java.programmer
Subject Re: Verifying a list is alphabetized
References (5 earlier) <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>
Message-ID <JOGdnZ4NAKmfkEHTnZ2dnUVZ_rednZ2d@earthlink.com> (permalink)

Show all headers | View raw

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

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Verifying a list is alphabetized laredotornado <laredotornado@zipmail.com> - 2011-11-30 07:52 -0800
  Re: Verifying a list is alphabetized Knute Johnson <nospam@knutejohnson.com> - 2011-11-30 08:05 -0800
    Re: Verifying a list is alphabetized Lew <lewbloch@gmail.com> - 2011-11-30 11:18 -0800
    Re: Verifying a list is alphabetized Arne Vajhøj <arne@vajhoej.dk> - 2011-12-02 19:54 -0500
      Re: Verifying a list is alphabetized Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-03 07:44 -0500
        Re: Verifying a list is alphabetized Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-03 09:02 -0500
        Re: Verifying a list is alphabetized Roedy Green <see_website@mindprod.com.invalid> - 2011-12-03 20:05 -0800
          Re: Verifying a list is alphabetized Roedy Green <see_website@mindprod.com.invalid> - 2011-12-03 22:13 -0800
            Re: Verifying a list is alphabetized Tom Anderson <twic@urchin.earth.li> - 2011-12-04 21:47 +0000
          Re: Verifying a list is alphabetized Martin Gregorie <martin@address-in-sig.invalid> - 2011-12-04 12:42 +0000
            Re: Verifying a list is alphabetized Patricia Shanahan <pats@acm.org> - 2011-12-04 12:18 -0800
              Re: Verifying a list is alphabetized Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2011-12-04 13:17 -0800
                Re: Verifying a list is alphabetized Patricia Shanahan <pats@acm.org> - 2011-12-04 15:32 -0800
                Re: Verifying a list is alphabetized markspace <-@.> - 2011-12-04 15:59 -0800
                Re: Verifying a list is alphabetized Patricia Shanahan <pats@acm.org> - 2011-12-04 16:14 -0800
                Re: Verifying a list is alphabetized markspace <-@.> - 2011-12-04 17:12 -0800
                Re: Verifying a list is alphabetized Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-04 21:17 -0500
            Re: Verifying a list is alphabetized Tom Anderson <twic@urchin.earth.li> - 2011-12-04 22:11 +0000
              Re: Verifying a list is alphabetized Martin Gregorie <martin@address-in-sig.invalid> - 2011-12-04 23:41 +0000
              Re: Verifying a list is alphabetized Roedy Green <see_website@mindprod.com.invalid> - 2011-12-12 01:39 -0800
          Re: Verifying a list is alphabetized Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-12-04 08:47 -0500
          Re: Verifying a list is alphabetized Gene Wirchenko <genew@ocis.net> - 2011-12-04 21:34 -0800
  Re: Verifying a list is alphabetized Patricia Shanahan <pats@acm.org> - 2011-11-30 12:52 -0800
    Re: Verifying a list is alphabetized laredotornado <laredotornado@zipmail.com> - 2011-12-01 06:43 -0800
  Re: Verifying a list is alphabetized Joshua Maurice <joshuamaurice@gmail.com> - 2011-11-30 13:16 -0800
  Re: Verifying a list is alphabetized Roedy Green <see_website@mindprod.com.invalid> - 2011-12-02 01:43 -0800
    Re: Verifying a list is alphabetized Patricia Shanahan <pats@acm.org> - 2011-12-02 05:58 -0800
      Re: Verifying a list is alphabetized Arne Vajhøj <arne@vajhoej.dk> - 2011-12-02 19:55 -0500
      Re: Verifying a list is alphabetized Roedy Green <see_website@mindprod.com.invalid> - 2011-12-03 02:54 -0800
        Re: Verifying a list is alphabetized Patricia Shanahan <pats@acm.org> - 2011-12-03 06:17 -0800
    Re: Verifying a list is alphabetized Roedy Green <see_website@mindprod.com.invalid> - 2011-12-03 03:10 -0800
  Re: Verifying a list is alphabetized Arne Vajhøj <arne@vajhoej.dk> - 2011-12-02 19:52 -0500

csiph-web