Find $\Theta$ for these two: $log_8(n^2), n^{\frac{1}{logn}}$

Question

Find $\Theta$ for these two: $log_8(n^2), n^{\frac{1}{logn}}$

The answers are: $log_8(n^2) = \Theta (log(n))$

For the second one it is $\Theta(1)$

Here's the solution for the second one which I entirely didn't understand:

$n^{\frac{1}{logn}} = m \rightarrow log(m) = \frac{1}{log(n)}log(n) = 1 \rightarrow m = 2 = \Theta(1)$

Taken from Intorudction to Algorithms $2$nd

Answer 1

For the first one, $$\log_8(n^2)=2\log_8(n)=2\cdot \frac{\log_2(n)}{\log_2(8)}=\frac{2}{3}\cdot\log_2 n.$$ For the second one, use the logarithm property: $a^b=2^{b\log_2 a}$. Then $$n^{\frac{1}{\log_2 n}}=2^{\frac{\log_2 n}{\log_2 n}}=2.$$

P.S. I assumed that you are interested in expressing all these numbers using the the binary logarithm $\log_2$.

Answer 2

$log(m)$ is of order $1$, which means that there are $k_1,k_2\in R$ and $n_0 \in N$, such that for all $n>n_0$

$k_2>log(m)>k_1$

In this case, we can take $k_1=0.5$, $k_2=2$ and $n_0=1$, because $log(m)=1$.

Considering the fact that exponential functions are monotonically increasing, take the inequality above to the power of the base of the logarithm (I have assumed it is $e$).

$e^{k_2}>m>e^{k_1}$

Now, the new $k_1$ and $k_2$ are $e^{k_1}$ and $e^{k_2}$, while you have the same $n_0=1$

Therefore, $m$ can be bounded by a polynomial of the form $f(x)=1$.