Time Complexity

While a process is competing for a resource it will loose at most one competition with each of its neighbours. The longest possible chain of neighbours that prevent each other from accessing a resource is n. Therefore a process has to wait in the worst case scenario until all other n-1 processes have entered their critical section once and received all fork messages. This gives a time bound for accessing a resource of O(n(l+d)).
 

11/16/1999