Existing complexity measures for concurrent algorithms typically consider the worst case [1, 3], and in rare instances the best case [4, 10], when estimating the number of steps required for an operation executed by a process to terminate.