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$>
References: <hqa8uu$g95$> <hqai74$qb$> <hqaipc$alq$> <hqampe$hme$>
Reply-To: <HIDDEN>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: 1271456240 2007 (16 Apr 2010 22:17:20 GMT)
NNTP-Posting-Date: Fri, 16 Apr 2010 22:17:20 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: comp.soft-sys.matlab:627359

"Roger Stafford" <> wrote in message <hqampe$hme$>...
>   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