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: Tue, 13 Sep 2011 08:33:29 -0500
Date: Tue, 13 Sep 2011 06:33:27 -0700
From: Patricia Shanahan <pats@acm.org>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.2.22) Gecko/20110902 Thunderbird/3.1.14
MIME-Version: 1.0
Newsgroups: comp.lang.java.programmer
Subject: Re: Using Java Classes to Sort a Small Array Quickly
References: <86c4a53b-1ca1-48a8-b954-c01bd449278a@s35g2000prm.googlegroups.com> <j3mupc$d5m$1@dont-email.me> <MPG.28d742f5c91d21e9896b8@202.177.16.121> <j4jala$dkh$1@dont-email.me> <MPG.28d76557830521d69896ba@202.177.16.121> <fuhs67lrl26ubtv16brfg56c4kueldb28k@4ax.com> <4e6e8f47$0$308$14726298@news.sunsite.dk> <j4mblo$p46$1@dont-email.me>
In-Reply-To: <j4mblo$p46$1@dont-email.me>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <rJSdncnl0vU0xvLTnZ2dnUVZ_oudnZ2d@earthlink.com>
Lines: 17
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 70.230.201.107
X-Trace: sv3-aEL62JI7ROplfwp0RDgFq8sn80GyDHr0kNWU8cQKLi0lghhhan8gcD/YdkIC7wfcFAEG9PuznJ8u9I5!9oyjdCU2SZPJq6CpHLi0BK+Z6+iKUfJPxJABxeMpPVQRfEQU+8NmGv/V8uaMhlPiC+fLDEkbXn22!55x4rawxwkwgkw2pAP9YDZtQ9I0EXXQtn3gNbIAYcA0WvlI=
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: 2072
Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:7969

On 9/12/2011 6:29 PM, Eric Sosman wrote:
...
> Big O is for whatever quantity it is measuring.
...

Another way of saying this is that Big-O is a relationship between
functions, that is, "f(x) is O(g(x))" is defined for a pair of functions
f and g.

Typically, f(x) is some measure of algorithm performance, such as the
worst case time for input of size x, and g(x) is a simpler function.

If f(x) is not the worst case time, I think it should be specified. If
f(x) is the worst case time and is O(g(x)) then the average and minimum
times are also O(g(x)).

Patricia