Are there algorithms with non-convex and non-concave computational complexity?

Question

If I am not mistaken, an algorithm that runs in time $\Theta(f(n))$ also runs in $\Theta(f(n) + a\sin(bn))$ where $a,b$ are conveniently chosen constants. Therefore I believe that the computational complexity of each algorithm can be described using a function that is neither convex nor concave.

However, this seems like a made-up case. Are there some algorithms, whose complexity in $\Theta$ notation can be described only using a non-convex non-concave function, or can each complexity be conveniently transformed to a convex or concave function?

Answer 1

Yes, there are algorithms whose complexity in $\Theta$ can only be described using a non-convex, non-concave function. Here's one such algorithm (that serves no practical purpose, but still).

• Read the length of the input $n$

• If $n$ is even, halt

• If $n$ is odd, loop for $n^2$ steps, then halt.

Suppose the complexity $T(n)$ of this algorithm is $\Theta(f(n))$, then there are $c,k$ so that for sufficiently large $n$, $cf(n)\leq T(n)\leq kf(n)$. Suppose (for contradiction) that $f$ is convex.

Let $n$ be odd and sufficiently large, we have that $2f(n)\leq f(n-1)+ f(n+1)$ (by concavity) and thus $\frac{2}{k}T(n)\leq\frac{1}{c}(T(n-1)+T(n+1))$. Substituting the original run time:

$$\frac{2}{k}(n+n^2)\leq\frac{2}{c}n$$

In other words, we have (up to some constants) $n^2\leq n$ which is a contradiction. So $f$ can not be convex, and by a similar argument can not be concave either.