The relabel operation can increase by at most . A saturating push on activates if it was inactive before the push, increasing by at most . Hence, the total contribution of all saturating pushes operations to is at most . A nonsaturating push on always deactivates , but it can also activate as in a saturating push. As a result, it decreases by at least . Since relabels and saturating pushes increase , the total number of nonsaturating pushes must make up the difference of . This results in a time bound of for the nonsaturating push operations.