non-monotonic complexity algorithm

Question

as a thought exercise, I try to think of algorithm which has nonmonotonic complexity curve. only thing I could think of was some algorithm with asymptotic solution in extremities.

Is there such algorithm, which has nonmonotonic complexity curve, which does not rely on asymptotic approximation?

Answer 1

I don't know what you mean by 'asymptotic approximation', but theoretically, it is easy to construct such 'algorithm'...

var l = non_monotonic_function(input.size);
for (var i = 0; i < l; ++ i)
   do_some_O1_stuff(i);