Asymptotic notations involving log and binomial coefficients

Question

I'd like to ask for the hints for part (1) and (3) in the exercise below.

I stuck completely at part (1). For part (3), I found a way to simplify $f(n)/g(n)$, but then the answer would depend on the constant $k$, and not all the conclusions about the asymptotic relationships between $f$ and $g$ could be drawn from there. So I don't think my approach is correct. Here's my working so far:

Please note that we use the following definitions of the asymptotic notations:

$ $

Answer 1

I can try.

As for (1), note that $2^{\log{x}} = x$.

Therefore,

\begin{align}n^{1/\log n} & = 2^{\log(n^{1/\log n})} \\ & = 2^{\left( \log n \right) \cdot \left( 1/\log n \right)} \\ & = 2. \end{align} So, $\log n$ asymptotically dominates $n^{1/\log n}$, as logarithms grow faster than constants.

As for (3), the "meaning" of big-theta, as it says, is that your function is bounded by two functions of equal asymptotic order. These two functions can differ by a constant factor.