0

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$$

pad11
  • 103
  • 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)? – Bobson Dugnutt Sep 30 '16 at 20:20
  • 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

     – pad11 Sep 30 '16 at 20:24
  • 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}$? – Bobson Dugnutt Sep 30 '16 at 20:30
  • Fixed the ns - we didn't go over limits so I figured there is no need. – pad11 Sep 30 '16 at 20:34
  • @pad11 What do you mean by we didn't go over limits? How do you expect to do this without limits? – Simply Beautiful Art Sep 30 '16 at 20:34
  • Just to be absolutely clear (sorry I didn't ask this in the first go): You mean $(\log n)^{\log n}$, right? – Bobson Dugnutt Sep 30 '16 at 20:36
  • Are we to assume $\log$ means base $e$ or base $10$. The principal is the same either way. – fleablood Sep 30 '16 at 20:36
  • In class, limits was not discussed at all. I have no idea how to handle it with limits. If that is the way to handle it, I'll see what I can read about it – pad11 Sep 30 '16 at 20:36
  • ... and what exactly are you supposed to be comparing and noticing about them. One is an expression. The other is another expression. What are we supposed to do with them? Express one in terms of the other? – fleablood Sep 30 '16 at 20:38
  • @Lovsovs: i fixed it – pad11 Sep 30 '16 at 20:38
  • @fleablood: I revised it but it's comparing growth – pad11 Sep 30 '16 at 20:39
  • typically how I've handled other examples is to take the logs on both sides or use algebra to cancel out stuff – pad11 Sep 30 '16 at 20:40
  • Is $\log n^{\log n}$ supposed to be $(\log n)^{\log n}$ or $\log(n^{\log n})$. – fleablood Sep 30 '16 at 20:40
  • @fleablood - I've revised it but it's the first one – pad11 Sep 30 '16 at 20:42

2 Answers2

2

$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.

fleablood
  • 124,253
  • I feel like a fool! $\ddot\smile$ – Simply Beautiful Art Sep 30 '16 at 20:50
  • 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) – pad11 Sep 30 '16 at 20:53
  • @pad11 See last couple of lines in my answer to see why it can be done. – Bobson Dugnutt Sep 30 '16 at 20:55
  • $(a^x)^y = a^{xy} = (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}$. – fleablood Sep 30 '16 at 22:23
  • 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. – fleablood Sep 30 '16 at 22:34
  • ok thanks @fleablood! – pad11 Oct 01 '16 at 00:00
1

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.$$

Bobson Dugnutt
  • 10,672