1
$\begingroup$

I understand that for two functions $f(n)$ and $g(n)$ for $n\in\mathbb N$, the notation $$g(n)=o(f(n)) \mbox{ as } n\rightarrow \infty$$ means that for all $\epsilon>0$, there exists $N\in\mathbb N$ such that $|g(n)|\le \epsilon |f(n)|$ whenever $n>N$, or equivalently, if $f(n)$ is non-zero for sufficiently large $n$ $$\lim_{n\rightarrow \infty} \dfrac{g(n)}{f(n)}=0.$$ And variants of the notation for real functions exist too.

However, I have seen many people who treats "$o(n)$" as some quantity. For example, they write things like $$g(n)=\left(f(n)+o\left(1/n\right)\right)^n.$$ This doesn't seem to make sense at all just looking at the definition. Can someone give me a rigorous definition of what an expression of this sort really means?

$\endgroup$
2
  • $\begingroup$ In those case, then mean "for some $h$ with $h(n)=f(n)+o(1/n)$, $g(n)=h(n)^n$." Or, equivalently, that $g(n)^{1/n}-f(n)=o(1/n)$. It is definitely abuse of the original notation (and the original notation abuses the "=" sign.) $\endgroup$
    – Thomas Andrews
    Nov 22, 2015 at 21:53
  • $\begingroup$ @ThomasAndrews why does it abuse the original notation? One could say the entire point of introducing that type of notation and writing it with = is to write things as asked about. $\endgroup$
    – quid ♦
    Nov 22, 2015 at 21:58

2 Answers 2

Reset to default
5
$\begingroup$

This means that $ g(n) = (f(n) + h(n))^n $ for some function $ h$ such that $h(n) = o(1/n) $.

$\endgroup$
1
  • 1
    $\begingroup$ I see. I'm surprised that I couldn't find any explanation of this on the internet despite its common usage. Thanks! (I love your name btw) $\endgroup$
    – Gawin
    Nov 22, 2015 at 22:09
3
$\begingroup$

This expression means that $g(n)=\left(f(n)+h(n)\right)^n$ where $h(n)$ is some (unspecified) function that is $o(1/n)$.

$\endgroup$

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.