noaktree 734 Report post Posted May 26, 2005 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. 0 Share this post Link to post Share on other sites
Guest Anonymous Poster Report post Posted May 26, 2005 If X is constant, then the complexity is O(log n). 0 Share this post Link to post Share on other sites
MaulingMonkey 1730 Report post Posted May 26, 2005 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). 0 Share this post Link to post Share on other sites
noaktree 734 Report post Posted May 26, 2005 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] 0 Share this post Link to post Share on other sites
Conner McCloud 1135 Report post Posted May 26, 2005 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 0 Share this post Link to post Share on other sites
noaktree 734 Report post Posted May 26, 2005 [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)? 0 Share this post Link to post Share on other sites
twanvl 512 Report post Posted May 26, 2005 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? 0 Share this post Link to post Share on other sites
noaktree 734 Report post Posted May 26, 2005 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. 0 Share this post Link to post Share on other sites
Guest Anonymous Poster Report post Posted May 26, 2005 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. 0 Share this post Link to post Share on other sites
noaktree 734 Report post Posted May 26, 2005 Excellent! Thanks everyone! ++ 0 Share this post Link to post Share on other sites
xEricx 572 Report post Posted May 26, 2005 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! 0 Share this post Link to post Share on other sites