2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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_+$. $\endgroup$ – Apass.Jack May 4 at 16:27
9
$\begingroup$

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))$.

$\endgroup$
1
$\begingroup$

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

$\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.