Non-monotonic time complexity algorithm

As a thought exercise, I am trying to think of an algor开发者_Python百科ithm which has a non-monotonic complexity curve. The only thing I could think of was some algorithm with asymptotic solution in extremities.

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

---

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

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

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

Designing an algorithm, one would probably find a way to pad the input data to remove non-monotonic behavior (i.e. accelerate smaller inputs), as is commonly done with fft.

---

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);

---

I don't think that there are many (any?) real algorithms like this, but just off the top of my head, in pseudo code:

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

This algorithm isn't asymptotic as n goes to infinity.