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.

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