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$?


No. A simple example is 
$$T(n)=\begin{cases}n &amp; \text{ when } n \text{ is odd,}\\
n^2 &amp; \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} &amp; \text{ when } n \text{ is odd,}\\
 2^{n^2}+1 &amp; \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))$.