3 ms·
How can an algorithm which sends O(n^2) messages between n nodes have O(log-star(n)) time complexity? I'm reading the paper now to try and understand, but it do
by titanomachy 11y ago
How can an algorithm which sends O(n^2) messages between n nodes have O(log-star(n)) time complexity? I'm reading the paper now to try and understand, but it doesn't seem possible to me. Doesn't O(n^2) messages mean each node send on average O(n) messages? Perhaps some subtlety of asymptotic notation escapes me here.
For those (like me) who didn't know, log-star is the iterated log function and grows very slowly: IteratedLog[2^65536] == 5.
- titanomachy 11y agoThe answer, of course, is in the paper: "time complexity" here doesn't have its usual meaning, but is defined as "the number of times a processor relies on the adversary to schedule a computation step or to deliver messages". The paper implies that this is the usual definition used in distributed systems analysis.