I need some explanation about the definition of ideal time complexity. My textbook says:

The ideal execution delay or ideal time complexity, T: the execution delay experienced under the restrictions “Unitary Transmission Delays” and “Syn- chronized Clocks;” that is, when the system is synchronous and (in the absence of failure) takes one unit of time for a message to arrive and to be processed.

What is intended for "Syncronized Clocks"?

Take for example broadcast problem and flooding protocol.

In this protocol each uninformed node wait that some informed node (at the beginning only the source) send to it the information and next it resend the info to all neighbors.

Now the ideal time complexity of this protocol is at most the eccentricity of the source and so at most the Diameter of the comunication graph.

Now if the ideal time complexity is this, necessarily al nodes send message to neighbor in parallel, correct?

and we are assuming that:

  • The source send message to each neighbor => 1 unit of time
  • The neighbors of the source send message to them neighbors => 1 time

and so on.. until we reach the most far away node from the source.

It's a correct view?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.