Jump to content
  • Advertisement
Sign in to follow this  
mike74

running time

This topic is 4834 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

If something has a running time of O( (log n)^2 ), is this asymptotically worse than O(n)? I'm pretty sure it is, but I guess it's usually better in practice, right? I just wanted to confirm. mike http://www.coolgroups.com/

Share this post


Link to post
Share on other sites
Advertisement
A not-so-rigorous way to decide would be to just pick a really big N. Like 10,000,000,000.

log(N) = 10, so log(N)^2 = 100. For this large N, log squared is smaller. It turns out that for larger N, the difference is even greater.

Share this post


Link to post
Share on other sites
for low values of N [say for example N=50, but it varies with the particular problem], O(N) is generaly faster than O(log(n)^2)

big-o notation is intended to describe how long something takes as N becomes large, for low values of N it's not very useful

[in general if there is an O(n^2) and a O(n log (n) ) the O(n^2) has less pre-computation and is faster for fewer than some number of elements]

Share this post


Link to post
Share on other sites
Alternatively, you can look at the ratio of the two terms as N approaches infinity, i.e.

lim (log(x))^2 / x as x -> inifnity.

Using L'Hopital's rule, this becomes

lim 2*log(x) / x = 0 (as x -> infinity).

So, x dominates (log(x))^2 in the limit and thus O(x) grows more quickly than O((log(x))^2).


-Josh

P.S. @John: how do you make those sexy sub/superscripts? [smile]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!