Prev: Pick random lines of a matrix ?
Next: Boxplot - Whiskers
From: Roger Stafford on 16 Apr 2010 18:02
"Asghar " <asgharally(a)hotmail.com> wrote in message <hqaipc$alq$1(a)fred.mathworks.com>...
> Well i had to time the elapsed time to sort out some randum numbers using bubblesort. I had to stop the random numbers to 10000 and plot time against numbers. And then i'm asked to find the time required to sort out by 1000000 and it says to find out by extrapolation. Is there any function for this? Would i get any meaningful answer?

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
From: John D'Errico on 16 Apr 2010 18:09
"Asghar " <asgharally(a)hotmail.com> wrote in message <hqakjh$d2i$1(a)fred.mathworks.com>...
> the curve isn't actually a proper one.. then i've used the polyval function and then did a line of best fit. i thought i could extrapolate that line using matlab. is there a way of obtaining the function of that line? and then i could just work it out without matlab by doing calculations for linear extrapolation.
>

If you have used polyfit, then polyval can evaluate the
function at ANY point. If that point is outside the
support of the data, then you are extrapolating.
Admittedly, extrapolation that far outside is generally
a meaningless operation.

So there should be no problem. Just use polyval, and
do the extrapolation as requested.

John
From: James Tursa on 16 Apr 2010 18:13
"Asghar " <asgharally(a)hotmail.com> wrote in message <hqaipc$alq$1(a)fred.mathworks.com>...
>
> Well i had to time the elapsed time to sort out some randum numbers using bubblesort.

Of course, bubble sort is pretty much the absolute worst possible sorting method ... I am going to assume that this is part of an exercise in demonstrating that.

James Tursa
From: Roger Stafford on 16 Apr 2010 18:17
"Roger Stafford" <ellieandrogerxyzzy(a)mindspring.com.invalid> wrote in message <hqampe$hme$1(a)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
From: Roger Stafford on 16 Apr 2010 18:29
"Roger Stafford" <ellieandrogerxyzzy(a)mindspring.com.invalid> wrote in message <hqanlg$1un$1(a)fred.mathworks.com>...
> 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

Come to think of it, as James has said, bubblesort is not very efficient and, in at least the worst case, tends to be order n-squared, so maybe you had better find the best fitting quadratic function in n instead of n*log(n).

It's hard to be sure, and that in turn should show you how unreliable this general kind of far-reaching extrapolation is likely to be.

Roger Stafford
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: Pick random lines of a matrix ?
Next: Boxplot - Whiskers