Sign in to follow this  

Algorithm Complexity

This topic is 4587 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
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
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
I never went to Uni so I never learned about this stuff, but Pragmatic Programmer has a section on algorithm complexity and I found it a very interesting read.

Actually, the whole book is interesting, you might wanna give it a try :)

Cheers!

Share this post


Link to post
Share on other sites

This topic is 4587 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this