Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: linear extrapolation
Date: Fri, 16 Apr 2010 22:17:20 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 12
Message-ID: <hqanlg$1un$1@fred.mathworks.com>
References: <hqa8uu$g95$1@fred.mathworks.com> <hqai74$qb$1@fred.mathworks.com> <hqaipc$alq$1@fred.mathworks.com> <hqampe$hme$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1271456240 2007 172.30.248.38 (16 Apr 2010 22:17:20 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Fri, 16 Apr 2010 22:17:20 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:627359

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <hqampe$hme$1@fred.mathworks.com>...
>   Now that you've told us this value is the time required in a bubblesort operation, that changes the whole picture.  It is known that optimum sorting requires a number of steps of the order of n*log(n) for sorting n numbers.  If we assume your bubblesort operation is anywhere near optimum, then the best assumption you could probably make would be to find a best fit - that is, pick the best value for a - for 
> 
>  t = a*n*log(n)
> 
> over the range from n = 1 to 10000, and use that for n = 1000000.  It still wouldn't be reliable but that's about the best you can do under the circumstances.
> 
> Roger Stafford

  Let me amend that last bit of advice a bit.  You should allow for some kind of fixed overhead on your calls to a bubblesort routine by getting the best a and b for t = a*n*log(n) + b, or else take only values of n from, say, n = 1000 to n = 10000, something like that.  The low values of n will probably be somewhat misleading for predicting extrapolated values.

Roger Stafford