2
$\begingroup$

This is the definition of the $\mathcal{O}$ notation in my textbook:

enter image description here

And I need to show the following:

enter image description here

Intuitively, I understand what the proposition tries to say is that because $|f(n)| \leq C . g(n) \, \forall n \geq n_o $, the difference between $C . g(n)$ and$|f(n)|$ for all $n \geq n_o$ will eventually offsets any difference between $f(n)$ and $g(n)$ for $n = 1,2,...,n_o-1$.

But, for example, if $\sum_{k=1}^{n_0-1} f(k) - g(k) > 0$, and $\forall n \geq n_o, |f(n)| = g(n) = 0$, wouldn't we still have $f(n) = \mathcal{O}(g(n))$, but there wouldn't be any $n_o'$ and $C'$ such that $\forall n \geq n_o'$, $\sum_{k=1}^{n}| f(k)| \leq C'.\sum_{k=1}^{n} g(k)$?

$\endgroup$
  • $\begingroup$ Your definition is incomplete. Most formulations require that $g(n) \not = 0$ for sufficiently large $n$. $\endgroup$ – enedil Jun 2 '18 at 23:04
0
$\begingroup$

From definition,$$\sum_{k=1}^{n}f(k)=O\left(\sum_{k=1}^{n}g(k)\right)$$ means there exists constant $n_0$ and $C$ such that for any $n\geq n_0$, $$\left|\sum_{k=1}^{n}f(k)\right|\leq C\sum_{k=1}^{n}g(k).$$

So suppose $f(n)=O(g(n))$. We have $$\begin{align*}\left|\sum_{k=1}^{n}f(k)\right|&\leq\sum_{k=1}^{n}\left|f(k)\right|\qquad \text{Triangle inequality} \\ &=\sum_{k=1}^{n_0-1}\left|f(k)\right|+\sum_{k=n_0}^{n}\left|f(k)\right|\\ &\leq\color{blue}{\sum_{k=1}^{n_0-1}\left|f(k)\right|}+C\sum_{k=n_0}^{n}g(k)\\ &\stackrel{?}{\leq}\color{green}{C\sum_{k=1}^{n_0-1}g(k)}+C\sum_{k=n_0}^{n}g(k)\\ &=C\sum_{k=1}^{n}g(k) \end{align*}$$

Your intuition is correct, but the example you gave doesn't fit some assumptions, i.e. $g(n)\ne0$ for a large $n$ (as enedil pointed out). In fact, for $n$ being large, the inequality holds, since the blue term will be a constant, and that the green one is also a constant as $n$ goes to $+\infty$. So in terms of asymptotic analysis, the theorem is true.

$\endgroup$
0
$\begingroup$

Yes, with this definition e.g.

$$f(k)=\begin{cases}1\text{ if }k=1\\ 0\text{ otherwise}\end{cases}$$ and $g(k)\equiv 0$ is a counterexample to the "fact".

Even modifying the definition of $O(\cdot)$ to say that $f(n)=O(g(n))$ if there are $n_0,C$ such that $g(n)\neq 0$ and $|f(n)|\leq Cg(n)$ for $n\geq n_0$ is not enough, since then you have a different type of counterexample using the same $f$ and $g(n)=(-1)^n$. Here $f(n)=O(g(n))$ by the new definition (with $C=0$), but $\sum_1^n f(k)$ and $\sum_1^n g(k)$ do not satisfy the new definition, since $\sum_1^n g(k)=0$ infinitely often.

What you need to add to the definition (which is fairly standard, e.g. see the Wikipedia article on big O) is the requirement that $g(n)>0$ for $n$ sufficiently large.

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