Let\'s consider the cost model for flooding to be directly proportional to the t

Question

Let's consider the cost model for flooding to be directly proportional to the total number of times nodes have to process a packet (either send or receive). What is the order of the worst and best case cost of sending a message from any node to any other node (not including reply messages) within this model? What are the topologies that produces these two cases? Assume there are N nodes in the network: the answers should be in terms of 0(f(N)). Trivial cases such as node A sends to node B, which is its only neighbor, will not be accepted, because they cannot be generalized!

Explanation / Answer

We know that there are N nodes ,

In the worst case , Each message will take N-1 time to be transferred to the other Node
and if there are N messages, The total time will be O(N2)

In the best case , Each message will take 1 time to be transferred to the other Node
and if there are N messages, The total time will be O(N)

Worst case: O(N2)

Best case: O(N)

Thanks, let me know if there is any doubts/concern.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.