0
$\begingroup$

I'm not that familiar with logs in general so not sure how to handle when say comparing two functions to see which one would grow slower / faster

$$n^{\log\log n}$$

to this...

$$(\log n)^{\log n}$$

Anyone able to help clarify? Just not sure what I should be doing when a log is in the exponent. I've only dealt with functions that have a base that is the same as the base of the function. For example...

$$2^{\log_2 9} = 9$$

$\endgroup$
  • $\begingroup$ I'm not sure what you're asking. What do you mean by "comparing"? "what I should be doing when a log is in the exponent" is also a tad unspecific - why should you do anything? Could you perhaps give an example of your problem(s)? $\endgroup$ – Bobson Dugnutt Sep 30 '16 at 20:20
  • $\begingroup$ It's just comparing different functions to see which grow faster. Similar to this... math.stackexchange.com/questions/1382947/how-to-recognise-intuitively-which-functions-grow-faster-asymptotically?rq=1 Where the person has similar functions but the response leaves it as (how?) for an explanation. found it after I posted...trying to make sense of it $\endgroup$ – pad11 Sep 30 '16 at 20:24
  • $\begingroup$ Okay. Have you tried using the answer to the question you linked to (i.e. taking the limit)? Also, there is no $n$ in your second equation.. do you mean $\log n^{\log n}$? $\endgroup$ – Bobson Dugnutt Sep 30 '16 at 20:30
  • $\begingroup$ Fixed the ns - we didn't go over limits so I figured there is no need. $\endgroup$ – pad11 Sep 30 '16 at 20:34
  • $\begingroup$ @pad11 What do you mean by we didn't go over limits? How do you expect to do this without limits? $\endgroup$ – Simply Beautiful Art Sep 30 '16 at 20:34
0
$\begingroup$

You want to compare which of the functions $f(n)=n^{\log \log n}$ and $g(n)=(\log n)^{\log n}$ grows faster. To determine this, let's look at their ratio (where $\log$ is assumed to be the natural logarithm and $t=\log n$) $$\frac{f(n)}{g(n)}=\frac{n^{\log \log n}}{(\log n)^{\log n}}=\frac{(e^t)^{\log t}}{t^t}=\frac{e^{t \log t}}{e^{t \log t}}=1,$$

and hence they grow at the same rate!

To show $t^t=e^{t \log t}$, let's solve $$t^t=e^{kt}=(e^k)^t \implies t=e^k \implies k=\log t.$$

$\endgroup$
  • $\begingroup$ ok thank you. I think I got it. Do you mind me asking how you get e^t from n? $\endgroup$ – pad11 Sep 30 '16 at 21:04
  • $\begingroup$ is it that you're using log base e as well? so that e^(log_e n) just means n? $\endgroup$ – pad11 Sep 30 '16 at 21:36
  • $\begingroup$ @pad11 Yes indeed. $\endgroup$ – Bobson Dugnutt Sep 30 '16 at 23:55
  • $\begingroup$ ok thanks for the help! $\endgroup$ – pad11 Sep 30 '16 at 23:56
2
$\begingroup$

$n^{\log \log n} =(e^{\log n})^{\log \log n}=(e^{\log \log n})^{\log n} = (\log n)^{\log n} $

so they are the same thing.

$\endgroup$
  • $\begingroup$ I feel like a fool! $\ddot\smile$ $\endgroup$ – Simply Beautiful Art Sep 30 '16 at 20:50
  • $\begingroup$ Ok mind if I ask what property you're using? I'm not sure why you can switch out n for e^log n and then back to log n at the end. Sorry, I haven't touch this sort of stuff in a while and it was brushed over quickly in class with very basic examples (no logs as exponents) $\endgroup$ – pad11 Sep 30 '16 at 20:53
  • $\begingroup$ @pad11 See last couple of lines in my answer to see why it can be done. $\endgroup$ – Bobson Dugnutt Sep 30 '16 at 20:55
  • $\begingroup$ $(a^x)^y = a^{x*y} = (a^y)^x$ so $n^{\log(gump)} = (e^{\log n})^{\log(gump)} = e^{\log n * \log(gump)} = (e^{\log(gump)})^{\log n} = gump^{\log(n)}$. So that's a neat little result I've never noticed: $a^{\log b} = b^{\log a}$ because $a^{\log b} = e^{\log a*\log b} = b^{\log a}$. Maybe I did learn that in high school and since have forgotten it the it is VERY neat, I think. So $n^{\log (\log n)} = (\log n)^{\log n}$. $\endgroup$ – fleablood Sep 30 '16 at 22:23
  • $\begingroup$ Basic definition: $a = b^{\log_b a} ; a = \log_b b^a= a\log_b b = a$. So if you need to compare $b^x ? a^y$ so can do $b^x = e^{x\log b}; a^y = e^{y\log a}$ and compare $x\log b$ vs $y\log a$ if its any easier. Likes comparing $a$ vs $ \log x$ we can do $a = \log e^{\log a}$ and compare $\log a$ vs. $x$ if it's any easier. $\endgroup$ – fleablood Sep 30 '16 at 22:34

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.