Papadimitrou and standard landau notation
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.