0

I'm trying to compare the Dijkstra's Algorithm to a Breath First Search Algorithm. After looking at the pseudocode and details about each, I've found that the complexities are:

Dijkstra's Algorithm - O(#Vertices * log(#Vertices) + #Edges)

Breath First Search - O(#Vertices + #Edges)

how can I tell which is more optimal? To simplify this we would basically be comparing: O(n*log(n)) with O(n) (if I'm not mistaken). However, I'm still unsure which is more efficient.

DannyD
  • 2,732
  • 16
  • 51
  • 73
  • Talking about which one is more efficient makes little sense, as they don't do the same thing. –  Dec 26 '13 at 18:25
  • if I wanted to use BFS to find an optimal path between two nodes? would that not be the same then? – DannyD Dec 26 '13 at 18:26
  • O(n*log n) < O(n) in algorithms. So the most efficient (just as a term) will be O(n*log n) – Cole Busby Dec 26 '13 at 18:27
  • 1
    BFS only finds optimal paths in the sense of featuring the fewest vertices. This only matches the paths found by Dijkstra's if the graph is unweighted (or equivalently, all weights are the same). But yes, then it would make sense to compare the two. –  Dec 26 '13 at 18:28
  • @ColeBusby I'm still finding other sources that say that O(n*lg(n)) > O(n). http://stackoverflow.com/questions/7830727/n-log-n-is-on. Could you clarify why you think O(n) is not more efficient? – DannyD Dec 26 '13 at 18:40
  • 1
    O(n * log(n) ) > O(n) for n > 10 (assuming log is base-10 logarithm) Take n = 100: 100 * log(100) == 100 * 10 == 1000. 1000 > 100. – antiduh Dec 26 '13 at 18:50
  • 1
    @antiduh - the logbase10(100) =2 not 10 – Mike Dinescu Dec 27 '13 at 16:00

1 Answers1

0

When doing Big-O analysis on graph algorithms it usually makes sense to include both the number of Edges and the number of Vertices as relevant variables in the expression, unless you know the graph is such that the number of Vertices dominates the number of Edges (or vice-versa). So usually you don't want to say that an algorithm that has a Big-O complexity of O(E+V) can be reduced to O(n) (again, unless either E >> V or V >> E).

That said, as others have pointed out in comments, Djikstra's algorithm does something different than a Breadth First Search algorithm in case the graph is weighted so it only makes sense to compare them when applying to unweighted graphs.

Also, it was pointed out in the comments that O(n) dominates O(n*logn) for big values of n. This means that as n gets large, n*logn will always be larger than n. This can be studied by taking the limit as n approaches infinity of n / (n*logn) and observing that the limit is 0 which means that the denominator dominates the numerator asymptotically.

The complication in the case of graphs is that you are not comparing f(n) and g(n), but almost always it's going to be f(E,V) and g(E,V) so, in your case you are looking at: O(V+E) and O(V*logV + E). Luckily, this is a pretty easy case because the two expressions are almost the same, except for the logV factor. Since the E term is common on both sides, you are really just looking at the same O(V * logV) versus O(V) comparison discussed above. But things would get messier if you had to compare an algorithm with complexity O(V * logE + E) against another with complexity O(E * logV)

Mike Dinescu
  • 54,171
  • 16
  • 118
  • 151