2

I am trying to compare the growth rates of functions to review my understanding of basic Algorithms. The text asks to compare:

$$N\log \log N$$

and

$$N\log^2{N}$$

Are they not the same function?

Clayton
  • 24,751
Thalatta
  • 155
  • 2
    I would say so. But it could also be $(\log N)^2$ - though less used than your verdict. – Chinny84 Nov 03 '15 at 18:33
  • 5
    $\log^2N$ is common notation for $(\log N)^2$ (compare $\sin^2x=(\sin x)^2$, for example). – Clayton Nov 03 '15 at 18:35
  • 2
    @Chinny84 I would say exactly the opposite - the meaning as $(\log N)^2$ is much more common, particularly in complexity theory, than the meaning as $\log\log N$. Iterated logarithms, when they're used in e.g. analytic number theory, are generally written as $\log^{(k)}N$ if anything. – Steven Stadnicki Nov 03 '15 at 18:38
  • @stevenStadnicki Not my field. But it is good to know. I used the wrong words as I tend to use the example I gave rather than OP. But at the same time I never really gave it much thought before, and was a context thing usually. +1 to you. – Chinny84 Nov 03 '15 at 18:42

2 Answers2

5

Asking to compare $N\log(\log(N))$ with $N\log^2(N)$ would be useless if $\log^2(N)$ meant $\log(\log(N))$, therefore it most likely means $\log(N)^2$, i.e. $\log(N)\times\log(N)$, although I would avoid using that notation at all as being ambiguous. The first function grows slower. N log(N)^2 vs N log(log(N))

dbanet
  • 1,413
2

$\log^2N$ is common notation for $(\log N)^2$ (compare $\sin^2x=(\sin x)^2$, $\cos^2x=(\cos x)^2$, etc. for example).

If we are talking about iterated logarithms, $\log_{j+1}N=\log(\log_jN)$ with $\log_1N=\log N$ is common (at least in analytic number theory). @StevenStadnicki also notes that a common alternative is $\log^{(j)}N$ to denote the $j$-fold iterated logarithm.

Clayton
  • 24,751
  • As noted above, I've also seen $\log^{(k)}N$ used regularly for the iterated logarithm; this in particular saves confusion with the log-to-base-$b$ notation $\log_bN$. – Steven Stadnicki Nov 03 '15 at 18:39
  • @StevenStadnicki: Noted; thanks. I haven't seen this format in the literature (but I'm by no means an expert yet, either). – Clayton Nov 03 '15 at 18:40