Papadimitrou and standard landau notation

Question

This is a homework. I'd appreciate if you didn't give away answer straightaway but instead pointed me to the right direction.

From huge majority of sources the definition of $\mathcal{O}(n)$ is:

$f, g : N \to R^+$

$f \in \mathcal{O}(g) \Leftrightarrow \exists{c,n_0} \in N \> \forall n > n_0 : f(n) \leq c\cdot g(n)$

but in Papadimitriou's book there is a different definition I haven't seen anywhere before:

The order of $f$, denoted $\mathcal{O}(f)$, is the set of all functions $g:N\rightarrow N$ with the property that there are positive natural numbers $c>0$ and $d>0$ such that, for all $n\in N$, $g(n) \leq c \cdot f(n)+d.$

I assume the first definition evaluates the functions as continuous functions whereas the second definition is concerned only about the points on $n \in N$. Therefore undefined values that asymptotically goes to $\pm\infty$ are not an issue anymore.

For example if we take $f(n)=\frac{1}{n}$ and $g(n)=1$. We know that $f(n)\in g(n)$ because $\lim_{x\to\infty}\frac{\frac{1}{x}}{1}=0$. We find the value for $f(1)$ and raise the $g(n)$ above this point such as: $f(n) \leq 6\cdot f(n)$ or $f(n) \leq f(n)+6$

Is my assumption correct? If it is how can I prove this equivalence?

Answer 1

The two definitions are not equivalent. However, the case where they aren't equivalent is one that we aren't interested in for algorithm analysis.

The standard definition implies the Papadimitriou definition. The proof is fairly straightforward, by following the definitions carefully.

Suppose that $\exists c, n_0 \in \mathbb{N}, \forall n \gt n_0, f(n) \le c \cdot g(n)$. Let $c$ and $n_0$ be such constants. We want to prove that there exist $c',d' \in \mathbb{N}^*$ such that $\forall n \in \mathbb{N}, f(n) \le c' \cdot g(n) + d'$. Take $c' = c$ and $d = \max\{f(x) \mid x \le n_0\}$. If $n \le n_0$ then $f(n) \le d'$; if $n \gt n_0$ then $f(n) \le c \cdot g(n)$. Either way, for any $n \in \mathbb{N}$, $f(n) \le c' \cdot g(n) + d'$.

The converse is not true. Again, unfolding the definition works up to a point, but then one little extra assumption is needed to make the proof go through.

Suppose that we have $c', d'$ such that $\forall n \in \mathbb{N}, f(n) \le c' \cdot g(n) + d'$. We want to find $c$ and $n_0$ such that $\forall n \ge n_0, f(n) \le c \cdot g(n)$. If there is an $n_0$ such that $\forall n \ge n_0, g(n) \ge 1$, then we can factor $g(n)$: for any $n \ge n_0$, $f(n) \le (c' + d'/g(n)) g(n) \le (c' + d') g(n)$, so we can take $c = c' + d'$.

The case where this proof fails is when there is no $n_0$ such that $\forall n \ge n_0, g(n) \ge 1$, i.e. when there are infinitely many integers $x$ such that $g(x) = 0$. (More generally, for real-valued functions, the problem case is when there is a set of values $(x_k)_{k\in\mathbb{N}}$ such that $\lim_{k\to\infty} x_k = \infty$ and $\lim_{k\to\infty} g(x_k) = 0$. Equivalently, that means that $g$ has no positive infimum.) Under the Papadimitriou definition as quoted here, the order of such a function includes all constants, but under the standard definition, there has to be a cutoff point above which $f$ is zero when $g$ is zero. For example, take the function $g : \mathbb{N} \to \mathbb{N}$ defined by $g(x) = 1$ if $x$ is odd and $g(x) = 0$ if $x$ is even. The function $f(x) = 1$ does not satisfy $f \in O(g)$ under the standard definition, but it does under the Papadimitriou definition.

This corner case isn't important in algorithm analysis because complexity functions are never “really” zero. With space complexity, there's always a bit of stack space just for the function call. With time complexity, it takes a few instructions to call a function even if the function does nothing.

Answer 2

Here's a hint: we'll show that Definition 1 (the usual definition) implies Definition 2 (Papadimitriou's).

Suppose that $f\in\mathcal{O}(g)$, so for some $c, k>0$ we have $f(n)\le c\cdot g(x)$ for all $x>k$.

Define a new function $d(x)=c\cdot g(x)-f(x)$ and define $d=\min_{x>0}\{d(x)\}$, so $d\le d(x)$ for all $x>0$.

• If $d\ge 0$, then $c\cdot g(x)-f(x) \ge 0$ for all $x>0$ so $f(x)\le c\cdot g(x)<c\cdot g(x)+1$ for all $x>0$ and hence $f\in\mathcal{O}(g)$ by definition (2).
• If $d<0$, then since $c\cdot g(x)-f(x)=d(x)\ge d$ for all $x>0$ so $c\cdot g(x)-d-f(x)\ge 0$ for all $x > 0$ and so $f(x)\le c\cdot g(x)+(-d)$ for all $x > 0$ and since $-d>0$, $f\in \mathcal{O}(g)$ by definition (2).

A similar argument can be used to show the implication in the other direction.

Answer 3

The idea of $d$ is that you can say for all $n \in \mathbb{N}$ while within the other definition the inequality will hold after some $n$, such that $ n > k$.

Also, when we talk about algorithms we're mostly concerned with functions defined over the integers.

Edit: Let's try to prove both directions:

(traditional definition $\Rightarrow$ Papadimitriou's) Given $f,g : N \rightarrow \mathbb{R^+}$ : $\exists c>0,\delta >0$ and for $n \ge \delta$ the inequality $f(n) \le cg(n)$ is true. Let $d = \max_{n \in [0,\delta]}\{f(n) - cg(n)\}$ then the inequality $f(n) \le cg(n) + d$ is true for all $n$, from where the proof for this direction is done.

(Papadimitriou's $\Rightarrow$ traditional definition) Given $f,g : N \rightarrow \mathbb{R^{+}} : \exists \bar{c} > 0, \bar{d} > 0$ and for all $n \in \mathbb{N}$ the inequality $f(n) \le \bar{c}g(n) + \bar{d}$ holds. $$f(n) \le \bar{c}g(n) + \bar{d} = \bar{c}\left(g(n) + \frac{\bar{d}}{\bar{c}}\right) \Rightarrow f(n) \equiv O\left(g(n) + \frac{\bar{d}}{\bar{c}}\right) \equiv O\left(g\right)$$