4
$\begingroup$

Can someone explain why BFS is $O(V + E)$ whereas DFS is $\Theta(V + E)$. I understand the definitions of both notations, but I just don't see why the bound for DFS should be tighter than that of BFS.

Is it because DFS is guarenteed to visit all vertices and hence has the lower bound $\Omega(V+E)$?

Note: I am studying the CLRS book, which is where the running times is coming from

Improve this question
$\endgroup$
1
  • $\begingroup$ It is nice that a reference is provided. Thank you. $\endgroup$
    – John L.
    Commented May 18, 2019 at 16:02

1 Answer 1

Reset to default
3
$\begingroup$

The running time of both BFS and DFS are $\Theta(V+E)$ since both of them are guaranteed to visit every vertex and every edge at least once. Note that we are talking about the situation when the input graph is a connected graph whose edges are given by adjacency-list, the most common situation (in the course of your study).

It is not surprising that the CLRS book presents the running time of BFS as $O(V+E)$ even though $\Theta(V+E)$ is the optimal asymptotic bound for its running time. It is actually a general practice that the running time of an algorithm is described in term of big $O$ even though it might be possible to describe in term of big $\Theta$. The reason is that how tight we can bound the running time of an algorithm from above is the major concern for many situations.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your answer. Isn't it considered good practice to always describe the running time with the tighest bounds possible and use $\Theta$ notation where possible? $\endgroup$
    – Alex5207
    Commented May 19, 2019 at 7:56
  • 2
    $\begingroup$ Yes, it is a best practice to describe the running time with the tightest bounds possible. However, it takes more effort to arrive at the better description. If it is enough to describe with big $O$ notation,, it is not compulsory to go the extra mile. For example, in almost all complexity analysis for problems in programming tests, it is enough to show the upper bound by big $O$ notation, since all that matters is the program should run within the time limit. In the end, there is a trade off in almost every choice we have to make. $\endgroup$
    – John L.
    Commented May 19, 2019 at 8:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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