1
$\begingroup$

BFS and DFS can be achieved in O(|V| + |E|). I understand the proof but it seems a bit lengthy.

  • Can I argue O(|V| + |E|) in a very simply way? e.g. checking each edge at most once?
  • Also what does O(|V| + |E|) imply?

I know Dijstrka algorithm and many other algorithm is somewhat like BFS. Does it imply automatically they can be run in |V| + |E| is the lower bound?

$\endgroup$
  • 1
    $\begingroup$ "I understand the proof but it seems a bit lengthy." -- they aren't. I recommend you spend some time to understand these proofs. Otherwise you'll be completely lost when you enter more complex things. $\endgroup$ – Raphael Sep 24 '16 at 10:56
  • $\begingroup$ "checking each edge at most once? " -- that's a central part of the proof. $\endgroup$ – Raphael Sep 24 '16 at 10:56
  • 2
    $\begingroup$ "Also what does O(|V| + |E|) imply?" -- unfold the definition; what more are you looking for? $\endgroup$ – Raphael Sep 24 '16 at 10:56
  • 1
    $\begingroup$ "I know Dijstrka algorithm and many other algorithm is somewhat like BFS." -- define "somewhat like". Yes, every algorithm that considers each part of the input has input size as a lower bound on the running time. $\endgroup$ – Raphael Sep 24 '16 at 10:57
  • 1
    $\begingroup$ In total, I'm not sure there really is much of a question here. Community votes, please! $\endgroup$ – Raphael Sep 24 '16 at 10:58
1
$\begingroup$

Intuitively, what a time upper bound of $O(|V| + |E|)$ means is that you spend $O(1)$ time per each vertex and each edge. Taking as an example DFS, there is one recursive call per edge, and the procedure itself runs once per vertex. You can turn this into a full-fledged argument that proves the upper bound.

An upper bound of $O(|V| + |E|)$ is optimal for most graph problems – those that potentially require examining all vertices and all edges. What such an upper bound tells you is that your problem can be solved in the minimal possible time; an $O(|V| + |E|)$ algorithm is an asymptotically optimal algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.