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


I can try.

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.

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.

  • $\begingroup$ 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? $\endgroup$
    – ensbana
    Aug 11 '18 at 10:07
  • $\begingroup$ 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. $\endgroup$
    – Bladewood
    Aug 11 '18 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.