Jump to content
  • Advertisement
Sign in to follow this  
noaktree

Algorithm Complexity

This topic is 4892 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

Hi, I have an algorithm that preforms X number of O(log n) searches. What is the complexity of this algorithm? The item counts for every list searched are variable.

Share this post


Link to post
Share on other sites
Advertisement
Guest Anonymous Poster
If X is constant, then the complexity is O(log n).

Share this post


Link to post
Share on other sites
Depends on what X is, and how it's related to N :-).

Let's assume N is the size of a container or similar, and you're using a search algorithm that makes O(log N) checks.

Now, how does X scale?

If you do 10 searches when there's 100 values, and 100 searches when there's 1000 values, then X is a factor of N (X = N/10), and your algorithm then becomes O(N/10 log N) - and since constants don't matter, this is expressed as simply O(N log N).

On the other hand, if you do 10 searches when there's 1 value, and 10 searches when there's 100000 values, X is constant in relation to N (that is, you can't define X in terms of N) - in this case, your algorithm then remains O(log N).

Share this post


Link to post
Share on other sites
X is not constant it is also variable and has no relationship to N.

[Edited by - noaktree on May 26, 2005 4:21:38 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by noaktree
X is not constant it is also variable and has no relationship to N.

Then the answer is O(XlogN). Lots of graph algorithms end up with such a form, because they depend on both the number of nodes and the number of edges.

CM

Share this post


Link to post
Share on other sites
[Changed]

Ok so X can equal 5 and there are 200 items,
X can also equal 5 when there are 400 items.
X can also equal 2 when there are 400 items.

It is O(X log N)?

Share this post


Link to post
Share on other sites
Quote:
Original post by noaktree
I have an algorithm that preforms X number of O(log n) searches.

So X is the number of searches?
Quote:

Ok so X can equal 5 and there are 200 searches,

If X is 5 there are 5 searches? What is the relation of X to the algorithm exactly?

Share this post


Link to post
Share on other sites
Doh!!! I mean X = number of searches N = number of items per search.

Ok so X can equal 5 and there are N items,
X can also equal 2 when there are N items.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
It is O(X log N) then. Because the O-notation now has two variables in it, they can change independently like in your example and the formula will still hold.

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!