$\begingroup$

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?

$\endgroup$ 3

1 Answer

$\begingroup$

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.

$\endgroup$ 2

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy