3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.