Disproving: if $\sum_{i=1}^{n}f(i)=O\left(\sum_{i=1}^{n}g(i)\right)$ then $f(n)=O\left(g(n)\right)$

Question

I'm trying to disprove the following statement:

if $\sum_{i=1}^{n}f(i)=O\left(\sum_{i=1}^{n}g(i)\right)$ then $f(n)=O\left(g(n)\right)$

I tried to use the following functions:

$$ f(n)=\begin{cases} n & n\,odd\\ 1 & n\,even \end{cases},\,g(n)=\begin{cases} 1 & n\,odd\\ n & n\,even \end{cases} $$

For every $n\in\mathbb{N}$ even we get:

$$ \begin{align*} \sum_{i=1}^{n}f(n)&=f(1)+f(2)+\ldots+f(n)=\stackrel{0.5n}{\overbrace{1+\ldots+1}}+\stackrel{0.5n}{\overbrace{f(1)+f(3)+\ldots+f(n-1)}}\\&=0.5n+\sum_{i=1}^{0.5n}f(2i-1)=0.5n+\sum_{i=1}^{0.5n}2i=0.5n+2\cdot\frac{0.5n(0.5n+1)}{2}\\&=0.5n+0.5n(0.5n+1)=0.5n(2+0.5n)=\Theta(n^{2}) \end{align*} $$ For every $n\in\mathbb{N}$ odd we get: $$ \begin{align*} \sum_{i=1}^{n}f(n)&=f(1)+f(2)+\ldots+f(n)=\stackrel{0.5(n-1)}{\overbrace{1+\ldots+1}}+\stackrel{0.5(n+1)}{\overbrace{f(1)+f(3)+\ldots+f(n)}}\\&=0.5(n-1)+\sum_{i=1}^{0.5(n+1)}f(2i-1)=0.5(n-1)+\sum_{i=1}^{0.5(n+1)}(2i-1)\\&=0.5(n-1)+2\cdot\frac{0.5(n+1)(0.5(n+1)+1)}{2}\\&=0.5(n-1)+0.5(n+1)(0.5(n+1)+1)=0.5(n-1)\left(1+0.5(n+1)+1\right)=\Theta(n^{2}) \end{align*} $$

But what should I do next?

Answer 1

Recall that $f(n) = O(g(n))$ as $n\to\infty$ if and only if

$$\limsup_{n\to\infty} \left|\frac{f(n)}{g(n)}\right| < +\infty.$$

---

First, let $F(n) = \sum_{i=1}^n f(i)$ and similarly for $G(n)$. As you've defined $f$ and $g$, we have $F(2k) = G(2k)$.

Moreover, we have $F(2k+1) = F(2k) + 2k+1$ and $G(2k+1) = G(2k) + 1$. Hence, $F(2k+1) = G(2k + 1) + 2k.$ It folows that

$$\frac{F(n)}{G(n)} = \left\{\array{1&\text{if $n$ is even}\\ \displaystyle 1 + \frac{(n-1)}{G(n)}&\text{if $n$ is odd}}\right..$$

Since you've already shown $G(n)$ grows like $n^2$, we'll skip this step and conclude that $\lim_{n\to\infty} F(n)/G(n)$ exists and equals $1$, and hence that the $\limsup$ also exists and equals $1<\infty$, so we do have $F(n) = O(G(n))$.

---

On the other hand, we have

$$\frac{f(n)}{g(n)} = \left\{\array{\displaystyle \frac1n&\text{if $n$ is even}\\ \displaystyle n&\text{if $n$ is odd}}\right.,$$

so for the subsequence $a_n = f(2n+1)/g(2n+1)$ we have $\lim_{n\to\infty} a_n = +\infty$. It follows that

$$\limsup_{n\to\infty} \left|\frac{f(n)}{g(n)}\right| = +\infty,$$

so we do not have $f(n) = O(g(n))$.

Answer 2

If $f(n) = (-1)^nn$ and $g(n) = 1$ then $\sum_{k=1}^n f(k) = O(n)$ and $\sum_{k=1}^n g(k) = n$ but $|\dfrac{f(n)}{g(n)}| \to \infty $.