0

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

enter image description here

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:

enter image description here

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

enter image description here $ $ enter image description here

ensbana
  • 2,277

1 Answers1

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.

Bladewood
  • 615
  • 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? – ensbana 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. – Bladewood Aug 11 '18 at 19:08