0

I am trying to understand the small o notation and have come up the below exercises. Are they correct, as $n\rightarrow \infty $?

(1) $(n+1)/n=1+o(1/n)$

(2) $log(n+1)=log(n)+o(1/n)$

(3) $nlog(n)+nlog(log(n))=nlog(n)+o(n)$

(4) $o(n)o(1/n)=o(1)$, $o(n)o(1/n^2)=o(1/n)$, and $o(n^3)o(1/n)=o(n^2)$

LLT
  • 5
  • (1) $\frac{1}{n}\neq o(1/n)$, however it's a $o(1)$. Same for (2), $\log(1+1/n)\neq o(1/n)$. However, it's a o(1)$. (3) is wrong as well. – Surb Nov 07 '21 at 17:30
  • Those on the last line are correct, i.e. you can multiply o-terms like that. The rest are wrong. I'd suggest going back to the definition of little o notation and redoing your examples. – bjorn93 Nov 07 '21 at 17:33

1 Answers1

1

$$\frac{n+1}{n} - 1 = \frac{1}{n} $$

so the first one is incorrect since $\displaystyle{\frac{1}{n}}$ is not a $o \left( \displaystyle{\frac{1}{n}}\right)$.

2.$$\log(n+1) -\log(n) = \log \left( 1 + \frac{1}{n} \right) \sim \frac{1}{n}$$

so the second one is incorrect since $\displaystyle{\frac{1}{n}}$ is not a $o \left( \displaystyle{\frac{1}{n}}\right)$.

  1. $$n\log(n)-n\log(\log(n))-n\log(n) = n\log(\log(n))$$

which is not a $o(n)$, since $\displaystyle{\frac{n\log(\log(n))}{n} = \log(\log(n)) \rightarrow +\infty}$. So the third one is incorrect.

  1. Let $u_n = o(n)$, and $v_n = o \left( \displaystyle{\frac{1}{n}}\right)$. Then $$u_n v_n = \frac{u_n}{n} \times nv_n \longrightarrow 0 \times 0 = 0$$

so $u_n v_n = o(1)$.

The two other parts can be proved the exact same way. So option 4. is correct.

TheSilverDoe
  • 29,720