Algorithm Complexity
Author
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.
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).
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).
Author
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]
[Edited by - noaktree on May 26, 2005 4:21:38 PM]
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
Author
[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)?
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)?
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?
Author
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.
Ok so X can equal 5 and there are N items,
X can also equal 2 when there are N items.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
