# Logarithmic growth rates

I have this question in terms of grown rate (Computer Science Big-OH):

Rank the following three functions: $\log N$, $\log(N^2)$, $\log^2 N$. Explain.

I understand the first two are both $O(N)$ as $\log(N^2) = 2 \log (N)$. I am hoping someone can help explain to me what happens when you square a log. I am assuming this one will have the least growth rate? Also can someone mention on how to use the superscript so i don't have to use the carrot?

• By $\log^2 N$ do you mean $(\log N)^2$ or $\log (\log N)$? – Mark Viola Sep 14 '15 at 19:47
• You can see my edit for how I formatted the mathematical notation. In general you wrap any expression by "$\$\cdots\" and format with the mathJax syntax as described in the 'help' documentation – jameselmore Sep 14 '15 at 19:49
• ok thanks, I mean $(log N)^2$ – Peter3 Sep 14 '15 at 19:50

As you have noticed, $\log(N^2) = 2\log(N)$ and therefore $\log(N^2) \in O(\log(N))$.
Asymptotically, both grow slower than $\log(N)^2$, i.e. $\log(N) \in o(\log(N)^2)$.
Proof: For every positive constant $c > 0$, there needs to exists an $N^*$, such that $$c \log(N) < \log(N)^2.$$ for every $N \ge N^*$. As we can choose $N^* > 1$, $\log(N^*)$ is positive and monotonously increasing. Thus we can divide by $\log(N^*)$ to get: $$c < \log(N^*).$$ From this we can solve for $N^*$ using whatever base of the logarithm we agreed upon. Therefore, an appropriate $N^*$ exists and the statement follows.
• Which e symbol? If you mean $\in$, that is set membership. For example $1 \in \mathbb N$ means 1 is in the set of natural numbers. $f \in O(g)$ means that $f$ belongs to the set of functions that asymptotically grow no faster than $g$ (times a constant factor). – Andre Sep 15 '15 at 7:07