1
$\begingroup$

I have been looking at the question as to which grows faster asymptotically; $\log \sqrt n$ or $4 \log n$. I have applied L'Hopitals rule and ended up with 1/8. This would imply that they grow at same rate.

Graphically $4 \log n$ is always above $\log \sqrt n$. Also from a perspective that $4 \log n$ is $\log n^4$ would imply intuitively that growth of $4 \log n$ is faster asymptotically

There appear to be contradictions.

$\endgroup$
1
  • $\begingroup$ Also, 1/2 logn vs 4 logn they would appear to be same growth rate $\endgroup$
    – david
    Mar 1 at 10:21
2
$\begingroup$

The asymptotic growth of $4 \log n$ is referred to as $\Theta(\log n)$. You will have to look at the definition of asymptotic growth to see why that is the case, but intuitively, it is the growth of a function when we discard constant factors and only look at the function "in the limit".

You have found out that the difference between the two functions "is 1/8", which makes sense, and which would put these two functions in the same "growth class".

When it comes to $\Theta\left(\log ( \sqrt n ) \right)$, it is, as you likely have found out $$\Theta\left(\log ( n^{1/2} ) \right) = \Theta\left( \frac{1}{2}\log n \right) = \Theta\left(\log n \right).$$

$\endgroup$
1
  • 1
    $\begingroup$ I replaced $O(\cdot)$ with $\Theta(\cdot)$ since $f(n),g(n)=O(h(n))$ does not tell us anything about whether $f(n) = \Omega(g(n))$ and/or $f(n)=O(g(n))$. $\endgroup$
    – Steven
    Mar 1 at 10:39

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.