1

In Asymptotic Analysis by J.D.Murray on page 10 the following question is posed. If $f=O(g)$ show that: $$O(o(f))=o(O(f))=o(g)$$ I am really confused by what this actually means. How can you have $O(o(f))$? Surely $O$ has to act on a function and $o(f)$ is not a function - rather a statement about the function it equals. Please can someone explain.

Abe
  • 920
Quantum spaghettification
  • 2,362
  • 1
    Well, assume that $u\in o(f)$ and $v\in O(f)$. The first equality means $O(u)=o(v)$. –  Jul 25 '17 at 15:39
  • @Jack By $u\in o(f)$ do you mean a function $u$ such that $u=o(f)$? if not what do you mean - I have never seen $o(f)$ and $O(f)$ treated as sets before. – Quantum spaghettification Jul 25 '17 at 15:42
  • $o(f)$ and $O(f)$ are sets of functions with a certain growth condition depending of $f$… so the notation "$u = o(f)$" is kind of confusing… and it seems it confused you. How did you define $o(f)$ and $O(f)$ if not as sets? – Gono Jul 25 '17 at 15:44
  • @Gono I must admit I am new to this subject. The only way I have seen them defined is by the definitions given here http://www.math.illinois.edu/~ajh/595ama/ama-ch2.pdf. – Quantum spaghettification Jul 25 '17 at 15:46
  • @Gono what does $u=o(f)$ mean then in the context of sets? – Quantum spaghettification Jul 25 '17 at 15:48
  • @Quantumspaghettification: https://en.wikipedia.org/wiki/Big_O_notation#Matters_of_notation –  Jul 25 '17 at 15:52
  • 1
    Both notations mean the same… so if you write $u\in o(f)$ or $u = o(f)$ in both cases it holds $$\lim_{x\to\infty} \frac{u(x)}{f(x)} = 0$$. But I find the $=$-notation confusing because consider that with $u = o(f)$ also $2u = o(f)$ so you could naivly conclude $u = o(f) = 2u$ hence $u = 2u$ what's wrong… that's why the set notation should prefered especially if you are new to that topic… – Gono Jul 25 '17 at 15:55
  • @Gono Thanks, I understand the set properties of it now. I am still confused of what $O(O(f))=o(g)$ means. Does it mean the sets are equal (i.e. contain the same elements)? I ask since the next question asks to prove $O(f)O(g)=O(fg)$ but I have read the relation is acutally $O(f)O(g)\subseteq O(fg)$. – Quantum spaghettification Jul 26 '17 at 13:37

1 Answers1

0

As stated (Basin & Rusinowitch, 2004) in the context of O-notation the equals sign, $=$, means subset or equals, $\subseteq$. We then have to prove: $$O(o(f)) \subseteq o(O(f))\subseteq o(g)$$

Showing that $O(o(f))\subseteq o(O(f))$

To show this first statement we do as Jack's advice in the comments above. We let $u\in O(o(f))$ which means that: $$ \newcommand{\p}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\f}[2]{\frac{ #1}{ #2}} \newcommand{\l}[0]{\left(} \newcommand{\r}[0]{\right)} \newcommand{\mean}[1]{\langle #1 \rangle}\newcommand{\e}[0]{\varepsilon} \newcommand{\ket}[1]{\left|#1\right>} \newcommand{\bra}[1]{\left<#1\right|} \newcommand{\braoket}[3]{\left<#1\right|#2\left|#3\right>} |u| \le k|v| \text{ where } \lim_{x\rightarrow x_0} \l \f{v}{f}\r =0$$ But: $$\lim_{x\rightarrow x_0} \l \f{v}{f}\r =0 \Rightarrow \lim_{x\rightarrow x_0} \l \f{kv}{kf}\r =0 \Rightarrow \lim_{x\rightarrow x_0} \l \f{u}{kf}\r =0$$ Since $kf \in O(f)$ we have that $u\in o(kf)\in o(O(f))$. Hence every element $u\in O(o(f))$ is also in $o(O(f))$ meaning that $O(o(f))=o(O(f))$ i.e. $O(o(f))\subseteq o(O(f))$ .

Showing that $o(O(f))\subseteq o(g)$

Let $u \in o(O(f))$ then: $$ \lim_{x \rightarrow x_0}\l \f{u}{v}\r=0 \text{ where } |v|\le k|f|$$ but since $f\in O(g)$ we have that $|v| \le k_2 |g|$. This implies that: $$ \lim_{x \rightarrow x_0}\l \f{u}{k_2 g}\r=0$$ $$\Rightarrow \lim_{x \rightarrow x_0}\l \f{u}{ g}\r=0$$ Hence every $u\in o(O(f))$ is also in $o(g)$ meaning that $o(O(f))=o(g)$ i.e. $o(O(f))\subseteq o(g)$.

Community
  • 1
Quantum spaghettification
  • 2,362
  • Translating the property $u(x)=o(v(x))$, say when $x\to0$, as $$\lim_{x\to0}\frac{u(x)}{v(x)}=0$$ is problematic since it excludes cases such as $$u(x)=x\sin(1/x)\qquad v(x)=\sin(1/x)$$ for every $x\ne0$. The correct definition of $u(x)=o(v(x))$ when $x\to0$ is that there exists some function $w$ such that $u(x)=v(x)w(x)$ in a neighborhood of $0$ and $$\lim_{x\to0}w(x)=0$$ – Did Jul 30 '17 at 12:28
  • @Did, hmm I like this other definition - but I have never seen it before. Do you by any chance know of any sources that mentions it and where I can read up more? – Quantum spaghettification Jul 30 '17 at 12:36
  • @Did: Why it exclude the case you mentioned ? $$\lim_{x\to 0}\frac{u(x)}{v(x)}=\lim_{x\to 0}\frac{x\sin(1/x)}{\sin(1/x)}=\lim_{x\to 0}x=0.$$ – Surb Jul 30 '17 at 12:37
  • 1
    @Surb Because $v(x)=0$ for infinitely many $x$ close to $0$. – Did Jul 30 '17 at 12:38
  • 1
    @Quantumspaghettification The need to assume the function $v$ is not zero in a neighborhood of the limit point, if one insists on using the ratio definition, is already apparent on the corresponding WP page. – Did Jul 30 '17 at 12:48
  • ...One may also note the careful formulation here, clearly tailored to avoid ratios. – Did Jul 30 '17 at 12:56