Suppose I want to broadcast from my root to all the nodes in a BFS tree. What is the time complexity of this process? I know that it is suppose to be proportional to the depth of the tree, like O(Depth). A more formal way of saying this could be O(Diameter) or maybe O(Radius of the Root) if you want to be more specific.

However, these parameters do not provide any insight. O(Depth) or O(Diameter) could be O(n) if the tree were a line. Since BFS is not guaranteeing a balanced tree or a binary tree or whatever, it does not give any topological clue to me.

Should I say O(n) then? Or should I say O(Depth) to give a more precise answer?


You can say whatever you want as long as it is accurate. Both $O(n)$ and $O(\text{Depth})$ are accurate, so you can say either one. $O(\text{Depth})$ is more descriptive, since $\text{Depth} \le n$ always holds.

I don't know why you don't think it provides any insight; I think it does provide some potentially useful information.

  • $\begingroup$ I saw in several different academic sources that they rather use O(Diameter) than O(Depth). Is it because O(Depth) is intrinsically about the root, but O(Diameter) is bounding the analysis for the graph from a larger perspective; thus it is more general? $\endgroup$ – Ninja Bug Jul 2 '18 at 16:37
  • $\begingroup$ @NinjaBug, I've never seen that so can't comment on it. Lacking context, I don't know why someone would do that. $\endgroup$ – D.W. Jul 2 '18 at 16:57

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.