2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ CLRS has a similar definition to the first one but with the assumption that the functions are defined over the natural numbers instead of real numbers. $\endgroup$ – Giovanni Botta Dec 9 '14 at 16:19
  • $\begingroup$ Something is missing in the definitions, they are not equivalent. $\mathcal{O}(1)=\mathcal{O}(0)$ according to the second one, but not to the first. $\endgroup$ – Khaur Dec 9 '14 at 18:36
  • $\begingroup$ @Khaur Yes you were right. I forgot the limitations on functions. I edited my post. $\endgroup$ – Rudimentary Joe Dec 9 '14 at 18:48
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In your second proof there is $f(n) \leq (c'+d'/g(n))g(n) \leq (c'+d')g(n)$. It holds true for $g(n)=1$ But considering $g(n)<1$ wouldn't it be the other way around? $(c'+\frac{d'}{g(n)})g(n)\geq(c'+d')g(n)$ as $\frac{d'}{g(n)}>d'$? And also why did you put the $g(n)\leq 1$? $\endgroup$ – Rudimentary Joe Dec 10 '14 at 2:53
  • $\begingroup$ @RudimentaryJoe $g(n) \le 1$ was a typo, it should have been $g(n) \ge 1$. Having a positive minimum for $g$ is what makes the proof work. It doesn't have to be $1$, the proof would work (with a different $c$) as long as there exists an $\epsilon \gt 0$ such that $\forall n \ge n_0, g(n) \ge \epsilon$. $\endgroup$ – Gilles 'SO- stop being evil' Dec 10 '14 at 9:48
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This is what my opposite implication looks like: Assumption: $f\in \mathcal{O}(g)$, therefore for some $c,d>0$ the $f(x)\leq c\cdot g(x) + d$ holds true. Let's define a new set $N_r=\{x | f(x)=c\cdot g(x)\}$ of all roots for equation $f(x) = c\cdot g(x)$. Let $n_0 = max_{x>0}(n_r\in N_r)$. $f(x) \leq c\cdot g(x) \forall{x\geq n_0}$. $\endgroup$ – Rudimentary Joe Dec 9 '14 at 22:28
  • $\begingroup$ @RudimentaryJoe You didn't prove that $n_0$ exists. The set could be unbounded. $\endgroup$ – Gilles 'SO- stop being evil' Dec 10 '14 at 1:41
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ While this is true, I'm not quite sure how it answers the question. Could you maybe expand on your answer so it relates more closely to the question? $\endgroup$ – David Richerby Dec 9 '14 at 16:43
  • $\begingroup$ So the first definition is basically second one with $d=0$. Because we are satisfied with $g(n)$ growing faster than $f(n)$ in the long run? $\endgroup$ – Rudimentary Joe Dec 9 '14 at 16:45

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.