# Big-O-notations and Small-o-notations

$$a)$$ Determine for all pairs $$i$$ and $$j$$, $$i,j ∈ {1, ldots, 6}$$ whether for the ones given below functions $$f_i ∈ O(f_j)$$ or $$f_i ∈ o(f_j)$$ or neither of the two applies as $$n → infty$$:

$$f_1 = log(n),$$

$$f_2 = log(sqrt n),$$

$$f_3 = log(n + log(n)),$$

$$f_4 = sqrt{log(n)},$$

$$f_5 = loglog(n^{log(n)}),$$

$$f_6 = log_2(n)$$

$$b)$$ Show that for the functions $$f(n) = log(n!)$$ and $$g(n) = nlog(n)$$ it holds that
$$f ∈ O(g)$$ and $$g ∈ O(f)$$. In fact, $$f$$ and $$g$$ are even asymptotically equivalent.

I am confused about the big $$O$$ and small $$o$$. When is $$f_{i} ∈ O(f_j)$$ and when is $$f_i ∈ o(f_j)$$? How to prove asymptotic equivalence?