Non-monotonic time complexity algorithm

Question

As a mental exercise, I am trying to come up with an algorithm that has a non-monotonic complexity curve. The only thing I could think of was an algorithm with an asymptotic solution in the limbs.

Is there an algorithm that has a nonmonotonic complexity curve that does not rely on the asymptotic approximation?

Answer 1

The discrete Fourier transform comes to mind; if applied as follows, it would be non-monotonic (and intermittent):

if is_power_of_2(len(data)): return fft(data) return dft(data) 

since dft works in O (N ** 2) and fft works in O (N log N).

By developing an algorithm, one could find a way to put input to remove non-monotonous behavior (i.e. speed up smaller inputs), as is usually done with fft.

Answer 2

I don’t know what you mean by “asymptotic approximation”, but theoretically it’s easy to build such an “algorithm” ...

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

Answer 3

I do not think that there are many (some?) Real algorithms like this, but only from my head, in the pseudocode:

 void non_monotonic_function(int n) { System.wait( Math.sin(n) ); } 

This algorithm is not asymptotic, since n goes to infinity.