Fasctode - Sort estimating complexity and B&V

Avatar Zondertau wrote:

Discussion out of vote thread...

> > Just a though: If you want to estimate that algorithm become
> > quadratic, you can:
> >
> > - 1) with 1000 elements
> > - 1) with 5000 elements
> > - 1) with 10000 elements
> >
> > .. compare times and if they are above O(N*LOG N) or (N* (LOG N)^2),
> > wrote that time is not recently computable for N elements.
>
> Why are you suddenly speaking of complexity? We're not trying to
> estimate that.

Estimating complexity and needed time for N elements according
upper measurments we can stop original worst case sequence
for any algorithm if it eventually have quadratic complexity,
since any algorithm is allowed to challange (even Bubble).
Calculating time on few fixed ammount elements, we can
estimete complexity and needed for sorting N element for
current sequence. For example:

1. Original quicksort will not be executed on N (1 shl 22) sorted
elements sequence after this analyze and that will be noticed.
Estimated time will exceed fixed "reasonable time" and that will
be sign not to execute it on that sequence.

2. Bubble can be included as well, but it will not be executed
for (1 shl 22) elements.

This can be another possible way to stop algoritm if it is
too slow, without using threads (preserving stability of
measurements) or checking state in comparison function or
sort function itself.

Sasa
--
www.szutils.net
.

Relevant Pages

  • Re: Predicting the Future and Kolmogorov Complexity
    ... portion of a sequence or pattern based on what was already known. ... complexity" as defined and modified by those like Kolmogorov, Chaitin, ... The algorithm used to compute pi doesn't ...
    (talk.origins)
  • Re: For Sean Pitman: Review of "Meaningful Information"
    ... portion of a sequence or pattern based on what was already known. ... complexity" as defined and modified by those like Kolmogorov, Chaitin, ... The algorithm used to compute pi doesn't ...
    (talk.origins)
  • Re: For Sean Pitman: Review of "Meaningful Information"
    ... portion of a sequence or pattern based on what was already known. ... complexity" as defined and modified by those like Kolmogorov, Chaitin, ... The algorithm used to compute pi doesn't ...
    (talk.origins)
  • Re: Fasctode - Sort estimating complexity and B&V
    ... > Estimating complexity and needed time for N elements according ... > upper measurments we can stop original worst case sequence ... > since any algorithm is allowed to challange. ...
    (borland.public.delphi.language.basm)
  • Re: Chex Wat: Pi is "random" and "not predictable"?
    ... their output sequence. ... The fact is that an algorithm can also be used to ... first was about the probability of finding an apparent match. ... They may be matched within e at an infinite ...
    (talk.origins)