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?
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 \begin{equation} c \log(N) < \log(N)^2. \end{equation} 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: \begin{equation} c < \log(N^*). \end{equation} 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.
