CODEWITHSUNDEEP
c++algorithmtimetreebreadth-first-search
darkfall94
darkfall94

Reputation: 13

Understanding Time Complexity for tree traversal using BFS

I am trying to understand the time complexity when I traverse a tree with n nodes (not necessarily a binary tree) using BFS. As per my understanding it should be O(n^2) since my outer loop runs for n times i.e till the queue is not empty and since the tree contains n nodes. And my inner for loop has to keep adding the children associated with a particular node to the queue. (Every node has a dict which contains the address of all its children) So for example if root node has n-1 nodes (and thus all those nodes have no children further) then wouldn't the time complexity be n*(n-1) = O(n^2).

Is my understanding correct? Is there any way that this can be done in O(n) ? Please explain.

Upvotes: 0

Views: 1120

Answers (2)

TsReaper
TsReaper

Reputation: 855

Big-O notation means the upper bound of the time complexity. You can of course say that the time complexity of BFS is O(n2), but it's not a strict upper bound.

To get the strict upper bound, you can consider BFS like this: Each node will be added into the queue only once, and each node will be removed from the queue only once. Each adding and removing operation costs only O(1) time, so the time complexity is O(n).

EDIT

To implement the O(n) BFS on a tree, you can try to implement the following pseudo code.

procedure bfs(root: root of the tree)
    q := an empty queue
    push root into q

    while q is not empty
        v := the element at the head of q
        for u := children of v
            push u into q
        pop v out of q

Upvotes: 0

Evan Darke
Evan Darke

Reputation: 614

It's often more useful to describe the complexity of graph algorithms in terms of both the number of nodes and edges. Typically |V| is used to represent the number of nodes, and |E| to represent the number of edges.

In BFS, we visit each of the |V| nodes once and add all of their neighbors to a queue. And, by the end of the algorithm, each edge in the graph has been processed exactly once. Therefore we can say BFS is O(|V| + |E|).

In a fully connected graph, |E| = |V|(|V| - 1)/2. So you are correct that the complexity is O(|V|^2) for fully connected graphs; however, O(|V| + |E|) is considered a tighter analysis for graphs that are known to be sparse.

Upvotes: 1

Related Questions