2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But, how can we claim that $\beta$ won't change when we chose an appropriate $\gamma$ value. What I mean is, doesn't $\beta$ change with the newly defined potential function? $\endgroup$ – Silver Flash Jun 11 at 11:55
  • $\begingroup$ You cannot claim that with a "black box" argument. You need to get your hands dirty, inspect the proof, and verify that $\beta$ does not change. In this case the $\beta t(H)$ term you want to get rid of is not coming from the definition of the potential function but rather from the analysis of the function CONSOLIDATE on page 518. $\endgroup$ – Steven Jun 11 at 12:02
  • $\begingroup$ I understand. This gives some confirmation to what I suspected. But I am probably not going to bother with confirming the result. $\endgroup$ – Silver Flash Jun 11 at 12:07
  • $\begingroup$ @Steven Thanks for the answer. So the main point is that if we have a potential function defined as $\Phi=\lambda \text{ units}$ then as in Physics we have a certain value associated with the unit, so on converting the $\text{units}$ of potential function to the units of the cost (actual and amortized) we get the desired result of the overpowering. (The potential function is very close to the concepts in physics after, more over the authors themselves say that potential function is quite like the potential energy in physics.) $\endgroup$ – Abhishek Ghosh Jul 15 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.