I am a bit confused about the run time of traversing a tree vs traversing a graph. Usually the run time of traversing a tree is O(V) where v is the number of node in the tree (i.e postorder, inorder or preorder traversal) but for graph it is generally O(V+E) giving we are traversing each vertice and edge. But if O(V+E) that is true for graph, why is O(V+E) not true for tree as well since we are also traversing tree edges when doing tree traversal. Or vice versa, if O(V) is true for tree, why is it not true for graph as well as we are also visiting each node once?
1 Answers
why is O(V+E) not true for tree as well...?
Actually O(+) is also true for tree traversal, but this expression can be simplified in the case of a tree, because for a tree we have this equality:
= - 1
In other words, a tree has one less edge than it has nodes. So this means the following expressions are equivalent:
O(+) = O(2-1)
In big O notation, which describes asymptotical complexity, we only have to regard the term with the highest order, and its coefficient is not relevant. So this is equivalent to O(). We could also have said O() with a similar reasoning.
Or vice versa, if O(V) is true for tree why is it not true for graph as well...?
Because in general we don't have a relationship between and .
For instance, a dense graph will have many more edges than vertices. When traversing a graph, you typically visit a vertex and then check each of the edges that connect with this vertex to see if the connected neighboring vertex still needs visiting. So then the work to do is linear to the number of edges.
On the other hand, a disconnected graph (maybe a forest) may have many more vertices than edges. While traversing the graph you'll again want to check for each vertex which are its neighbors. In this case you will maybe find vertices that don't have neighbors at all, but the work needs to be done. So then you have at least work that is linear to the number of vertices.
To cover for both extremes, we can say that the complexity is O() where is whichever is the greatest, or . So we then have: O(max(, )). Note that this is equivalent to O(+).
Related