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?

  • $\begingroup$ By $\log^2 N$ do you mean $(\log N)^2$ or $\log (\log N)$? $\endgroup$ – Mark Viola Sep 14 '15 at 19:47
  • $\begingroup$ 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 $\endgroup$ – jameselmore Sep 14 '15 at 19:49
  • $\begingroup$ ok thanks, I mean $(log N)^2$ $\endgroup$ – 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 \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.

  • $\begingroup$ Thanks for breaking it out. dumb question but what exactly does the e symbol mean? $\endgroup$ – Peter3 Sep 15 '15 at 1:01
  • $\begingroup$ 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). $\endgroup$ – Andre Sep 15 '15 at 7:07

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.