Unknown asymptotic notation $(1 + O\Big(\frac{\log n}{n}\Big))\frac{2^n}{n}$

Question

I am reading through Boolean Function Complexity by Stasys Jukna and I stumbled upon this notation for asymptotic bounds:

$$C(f) \leq (1 + \alpha_n)\frac{2^n}{n} \;where\; \alpha_n = O\Big(\frac{\log n}{n}\Big)$$

What exactly does the equation on the right mean? I am quite uncertain on how to interpret it as I have never the asymptotic notation used like that before.

Answer 1

$\mathcal O\left(\dfrac{\log n}n\right)$ represents the entire set of functions that do not grow faster than $\dfrac{\log n}n$. If you replace $\alpha_n$ with any of these functions, then (according to the author) the inequality should hold. For example, one such function is $\dfrac 1n$ since $\dfrac 1n\in\mathcal O\left(\dfrac{\log n}n\right)$.

Answer 2

I am supporter of having formal definitions in mathematics. Only having them, then I understand words "faster", "tends", "grows" etc. So exact definition, taking non negative case, is: $$O(g) = \left\lbrace f:\exists C > 0, \exists N \in \mathbb{N}, \forall n (n > N \& n \in \mathbb{N}) (f(n) \leqslant C \cdot g(n)) \right\rbrace $$ So, when we want to prove, that some function $\phi \in O(g)$, we need to find two constants $C, N$.

In your case, if you want to show, that some function is element of set $O\left(\dfrac{\log n}n\right)$, for example $\alpha_n=\frac{100}{n}$, you should solve inequality: $$\frac{100}{n} \leqslant C \cdot\dfrac{\log n}n$$ and show, that it holds for $n>N$, for some $N \in \mathbb{N}$. In example we can take $N= \left \lceil e^{\frac{100}{C}} \right \rceil$.

As to your questions, then we have some standard properties for big-$O$ $$O(f) + O(g) = O(f+g)$$ $$C \cdot O(f) = O(C \cdot f)= O(f)$$ for exact proof you can see Arithmetic rules for big O notation, little o notation and so on...