# Algorithm Complexity

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

## 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 on other sites
If X is constant, then the complexity is O(log n).

##### 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 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 on other sites
Quote:
 Original post by noaktreeX 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 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 on other sites
Quote:
 Original post by noaktreeI 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 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 on other sites
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 on other sites
Excellent! Thanks everyone! ++

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 14
• 12
• 15
• 11
• 12
• ### Forum Statistics

• Total Topics
634153
• Total Posts
3015846
×