CODEWITHSUNDEEP
algorithmgraphbig-ocomplexity-theory
John Smith
John Smith

Reputation: 617

Which complexity is better?

Assume that a graph has N nodes and M edges, and the total number of iterations is k. (k is a constant integer, larger than 1, independent of N and M)

Let D=M/N be the average degree of the graph.

I have two graph-based iterative search algorithms.
The first algorithm has the complexity of O(D^{2k}) time.
The second algorithm has the complexity of O(k*D*N) time.

Based on their Big O time complexity, which one is better?

Some told me that the first one is better because the number of nodes N in a graph is usually much larger than D in real world.

Others said that the second one is better because k is exponentially increased for the first one, but is linearly increased for the second one.

Upvotes: 1

Views: 499

Answers (3)

maxim1000
maxim1000

Reputation: 6365

Big-O notation describes how a function grows, when its arguments grow. So if you want to estimate growth of algorithm time consumption, you should estimate first how D and N will grow. That requires some additional information from your domain.

If we assume that N is going to grow anyway. For D you have several choices:

  1. D remains constant - the first algorithm is definitely better
  2. D grows proportionally to N - the second algorithm is better

More generally: if D grows faster than N^(1/(2k-1)), you should select the first algorithm, otherwise - the second one.

Upvotes: 2

gnasher729
gnasher729

Reputation: 52538

For every fixed D, D^(2k) is a constant, so the first algorithm will beat the second if M is large enough. However, what is large enough depends on D. If D isn't constant or limited, the two complexities cannot be compared.

In practice, you would implement both algorithms, find a good approximation for their actual speed, and depending on your values pick the one that will be faster.

Upvotes: 0

sds
sds

Reputation: 60014

Summary

Neither of your two O's dominate the other, so the right approach is to chose the algorithm based on the inputs

O Domination

  1. The first it better when D<1 (sparse graphs) and similar.

  2. The second is better when D is relatively large

Algorithm Selection

The important parameter is not just the O but the actual constant in front of it. E.g., an O(n) algorithm which is actually 100000*n is worse than O(n^2) which is just n^2 when n<100000.

So, given the graph and the desired iteration count k, you need to estimate the expected performance of each algorithm and chose the best one.

Upvotes: 3

Related Questions