# All superlinear runtime algorithms are asymptotically equivalent to convex function?

Is it true that every algorithm with runtime complexity of $$T(n)=\Omega(n)$$ satisfies that $$T(n)=\Theta(f(n))$$ for some convex function $$f$$?

All the examples that I could think of satisfy the above mentioned requirement. For example, all polynomials are convex on $$\mathbb N_+$$. Additionally, $$n\log(n)$$ is convex from $$n=2$$ and on, so it's asymptotically equivalent to convex function.

• The polynomial $x^2-4x+4$ is not convex on $\Bbb N_+$. You meant to say all polynomials with positive leading coefficient are eventually convex on $\Bbb N_+$. Or all polynomials with nonnegative coefficient are convex on $\Bbb N_+$. – Apass.Jack May 4 at 16:27

Is it true that every algorithm with runtime complexity of $$T(n)=\Omega(n)$$ satisfies that $$T(n)=\Theta(f(n))$$ for some convex function $$f$$?

No. A simple example is $$T(n)=\begin{cases}n & \text{ when } n \text{ is odd,}\\ n^2 & \text{ when } n \text{ is even.} \end{cases}$$

What if we also require $$T(n)$$ be strictly increasing?

The answer is still no. A simple example is

$$T(n)=\begin{cases}2^{(n+1)^2} & \text{ when } n \text{ is odd,}\\ 2^{n^2}+1 & \text{ when } n\text{ is even.} \end{cases}$$

Since $$\displaystyle\lim_{k\to\infty}\frac{T(2k)}{T(2k-1)}=1$$ and $$\displaystyle\lim_{k\to\infty}\frac{T(2k+1)}{T(2k)}=\infty,$$ there is no convex function $$f$$ such that $$T(n)=\Theta(f(n))$$.

Exercise 1. What if we also require both $$T(n)$$ be strictly increasing and $$T(n+1)/T(n)$$ be bounded?

Exercise 2. Let $$T_1$$ and $$T_2$$ be two increasing functions such that $$T_2(n)\not=O(T_1(n))$$. Show that there is a function $$T(n)$$ that is bounded between $$f_1$$ and $$f_2$$ such that there is no convex function $$f(n)$$ such that $$T(n)=\Theta(f(n))$$.

No. Consider $$T(n) = n$$ if $$n$$ is even, $$T(n) = 2^n$$ if $$n$$ is odd.