# Asymptotic notations involving log and binomial coefficients

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:



As for (1), note that $2^{\log{x}} = x$.
\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.
• Thanks. Your hint, and also these cases that involve the log, seems to use extensively of the formula: $b^{log_ad}=d^{log_ab}$. I found this formula on wikipedia but don't know how to prove it. Could you clarify? Aug 11 '18 at 10:07
• It's just the use of the definition of logarithms as the inverse (i.e. $\log(2^x) = 2^\log{x} = x$, over an appropriate domain) of exponential functions (since here logarithms are explicitly to base-2), along with the power rule of logarithms ($\log_a (b^c) = c \log_a b$). See this Wikipedia page. Importantly, remember that the logarithm of a product is the sum of the logarithm of each factor. Aug 11 '18 at 19:08