Order notation subtractions in Fibonacci Heap

Question

Can order notation on its own imply:

$O(D(n)) + O(t(H)) - t(H) = O(D(n))$

My guess is that you cannot since the constant in the O(t(H)) would still exist after the subtraction if the constant is > 0.

Well, this is actually the case, but there are underlying factors. This equation appears in Fibonacci heap analysis in CLRS (518). The justification for this step comes from the underlying potential function. According to the authors, "we can scale up the units of potential to dominate the constant hidden in $O(t(H))$". I want to know how this happens, but don't really know how to ask this complicated question.

Answer 1

As you point out your first equation is not necessarily correct.

Let me rewrite it by explicitly adding the multiplicative constants: $\alpha D(n) + \beta t(H) - \gamma t(H) = O(D(n))$, where $\gamma =1$. Here the problem is that $\beta$ might be larger than $\gamma = 1$.

What the authors are saying is that instead of thinking that one unit in the value of your potential function $\Phi(H)$ contributes one unit of potential, you can imagine that it is actually representing $\gamma$ units of potential. This amounts to redoing the analysis with a new potential function $\Phi'(H)$ defined as $\Phi'(H) = \gamma \cdot \Phi(H)$. If you do so, then you are able to control the value of $\gamma$ in the above equation, while $\beta$ stays the same.

Picking a value of $\gamma \ge \beta$ ensures that $\alpha D(n) + \beta t(H) - \gamma t(H) = \alpha D(n) - \underbrace{(\gamma -\beta)}_{\ge 0} t(H) \le \alpha D(n) = O(D(n))$, as desired.