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
    Commented Mar 1, 2021 at 10:21

1 Answer 1

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
    Commented Mar 1, 2021 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.