Re: Challenging problem

Markus Triska wrote: 
Hi Bart!

Bart Demoen wrote:

First: concluding from two measurements for each algorithm that the
asymptotic behaviour of one is better than the other ... this is wrong


It is unclear whether you think that Nameless arrived at that conclusion - I think it didn't. 

I indeed think that Nameless arrived at that conclusion. If you see
another interpretation of what (s)he wrote, please tell us.


Complexity theory


In this case it seems to be more interesting to discuss, for example, the average space requirements of the stated programs for some range of (arbitrary size) integers rather than upper bounds for their time complexities. One will then see that the O(N) time complexity version also has its drawbacks. 

Whether discussing space or time complexity is more interesting ...
perhaps a matter of taste. I find them both very exciting :-)

Same about average versus worst case complexity.

Perhaps clarify to us what you mean by "some range of (arbitrary size)
integers" and also tell us about the drawbacks of the O(N) time version.

Thanks

Bart Demoen
.