Verifying complexity empirically

Hi
What would be the best way to verify complexity of an algorithm
empirically ?
Specifically we have ( n1 , t1) , (n2, t2) , ..... ( nx , tx) what
represent input size and average execution time for the algorithm. and
I want to verify that this algorithm is O(n*log n) but neither O(n)
nor (n^2).

In article
<83e367e2-317d-46b2-8436-cc5a12cb3c9f@2g2000hsn.googlegroups.com>,
kestrel <youssef.mohammed@gmail.com> wrote:

> Hi
> What would be the best way to verify complexity of an algorithm
> empirically ?

It can not be done in the general case.

> Specifically we have ( n1 , t1) , (n2, t2) , ..... ( nx , tx) what
> represent input size and average execution time for the algorithm. and
> I want to verify that this algorithm is O(n*log n) but neither O(n)
> nor (n^2).

Suppose the algorithm F is a black box: the only information you can get
from running it is the output, and the amount of time and space it took.
Since "complexity" is short for "asymptotic complexity", what you are
interested in is the behaviour of F as n grows without limit.
Regardless of the set of n_i that you have, it's possible that F behaves
one way (e.g., O(n)) for all n <= max {n_i}, and some other way (e.g.,
exp(n)) for greater n.


--
---------------------------
| BBB b \ Barbara at LivingHistory stop co stop uk
| B B aa rrr b |
| BBB a a r bbb | Quidquid latine dictum sit,
| B B a a r b b | altum viditur.
| BBB aa a r bbb |
-----------------------------

On Aug 30, 12:05*pm, kestrel <youssef.moham...@gmail.com> wrote:
> What would be the best way to verify complexity of an algorithm
> empirically ?
> Specifically we have *( n1 , t1) , (n2, t2) , ..... *( nx , tx) what
> represent input size and average execution time for the algorithm. and
> I want to verify that this algorithm is O(n*log n) but neither O(n)
> nor (n^2).
As Barb Knox already pointed out, this is not possible in the general
case. It is, however, possible to do curve fitting on the pairs you
get, for comparing the efficiency of algorithms on real-life data.
I've tried that with a number of list representations (java.util.*),
and found two problems: first, it is very hard to get good runtime
measures, as it is hard to repeat tests - if the test changes the data
structure (say, by inserting an element), a test repetition will
produce different results, and the single operation requires so little
time that it is impossible to get exact measurements - and second, you
have to know the kind of polynomial the curve fitting will require (I
used gnuplot, maybe there are others that can automatically try a
series of functions). Still, both problems can be accounted for and
you can use the results for chosing an algorithm that suites your
expected data/events best.
Nevertheless, for actually VERIFYING an algorithm, this approach will
most likely fail. For example, java.util.ArrayList will exhibit
constant time requirements for inserting an element (the element is
just added at the end of the preallocated array, and the end array
pointer is increased). Only after an increasing number of steps (when
the element count reaches 2^n) the array will be resized, taking a
vast number of steps, and making java.util.ArrayList a list
representation with a O(n) worst-case insertion time... but you will
hardly see the difference with regression analysis, as these events
are so rare. Maybe there is some way to fit a "worst-case curve", but
I am not aware of it.
If you want to really verify an algorithm, you have to add more
information to it. You can use a type system that ensures that you
cannot exceed certain complexity bounds, e.g. <http://
www.tcs.informatik.uni-muenchen.de/~mhofmann/lics99icfp.ps.gz>.

On Sun, 31 Aug 2008 07:20:57 +0200, Kalle07 <kalle07@live.com> wrote:

> On Aug 30, 12:05*pm, kestrel <youssef.moham...@gmail.com> wrote:
>> What would be the best way to verify complexity of an algorithm
>> empirically ?
>> Specifically we have *( n1 , t1) , (n2, t2) , ..... *( nx , tx) what
>> represent input size and average execution time for the algorithm. and
>> I want to verify that this algorithm is O(n*log n) but neither O(n)
>> nor (n^2).

> As Barb Knox already pointed out, this is not possible in the general
> case. It is, however, possible to do curve fitting on the pairs you
> get, for comparing the efficiency of algorithms on real-life data.

> If you want to really verify an algorithm, you have to add more
> information to it. You can use a type system that ensures that you
> cannot exceed certain complexity bounds, e.g. <http://
> www.tcs.informatik.uni-muenchen.de/~mhofmann/lics99icfp.ps.gz>.

Other works on the subject that you can find of interest are:
* "Size aware types" by O. Shkaravska, M. van Eekelen & al. (U. Nijmegen,
Netherlands)
In these papers, they describe a type system for programs whose output
always has size polynomial in the size of the input. For the type
inference phase, they build a test-based approach that is able to find the
polynomial after running a few tests, that is, basically, from the (n_i,
t_i) pairs you're speaking about. The type system ensure that the
polynomial relation always hold, hence the asymptotical problem is
dismissed. It speaks about space and not time, but the idea can probably
be adapted.
(After a quick search, i was unable to find the exact paper I was thinking
about, but earlier version and/or research reports can be found.)

* "Quasi-Interpretations" by J.-Y. Marion, J.-Y. Moyen (myself) & al. (U.
Nancy, Paris 13, Paris 7, France)
In these paper, we use quasi-interpretation to polynomially bound the
size of computed values and then use this bound to bound the time
complexity of programs. There is (currently) no test-based approach to
find the quasi-interpretation (they are found by syntactic observation of
the program). But precise bounds on the complexity can sometimes be
inferred (see the paper by R. Amadio & al.) There is a survey paper
(waiting for last modifications before publication) available from J.-Y.
Marion's homepage.

* The whole ICC (Implicit Computationnal Complexity) communauty more or
less focuses on this issue and this kind of problems. In addition to
Munich (Hofmann), Nijmegen, Nancy, Paris 13, there are also groups working
on the subject in Copenhagen (TOPPS, Jones), Oslo (Kristiansen), Tel-Aviv
(Ben-Amram), and in the US (Leivant, Royer, ...)

--
Hypocoristiquement,
Jym.

In article <83e367e2-317d-46b2-8436-cc5a12cb3c9f@2g2000hsn.googlegroups.
com>, kestrel <youssef.mohammed@gmail.com> writes
>Hi
>What would be the best way to verify complexity of an algorithm
>empirically ?
>Specifically we have ( n1 , t1) , (n2, t2) , ..... ( nx , tx) what
>represent input size and average execution time for the algorithm. and
>I want to verify that this algorithm is O(n*log n) but neither O(n)
>nor (n^2).
>
Given sufficient effort and attention to statistics, I could imagine you
showing that e.g. between n = 100 and n = 10000 95% of all runs will
take time Anlog(n) +/- B%, at a confidence level of 80%. There is some
precedent for experiments on complexity; In "The Stanford Graphbase"
Knuth proposed counting references to memory as a processor-independent
measure of complexity, and provided a collection of graphs on which
experiments might be done. There is a "Journal of Experimental
Algorithmics", or something like that, which I have not read.

The big problem with this approach is that complexity is typically
reported as the worst case cost of the algorithm, over all possible runs
with a given input size n. Verifying worst case behaviour experimentally
will be extremely difficult.

To me, one of the most impressive feats of algorithm design is not just
that the algorithm is fast, but that it can be analysed and shown to be
fast. In fact, I suspect that some algorithms have been designed by
starting with something that could be analysed and then fiddling with it
until it was fast, rather than starting with something somebody hoped
might be fast and fiddling with it until it could be analysed.
--
A.G.McDowell