Amortized time complexity: DecreaseKey() in Fibonacci Heap

62 Views Asked by At

At Wikipedia we can find a description of DecreaseKey(). From my point of view, if we perform the operation of cutting the nodes or remarking them, it may take linear time complexity, depending on the height of the tree from which we are cutting subtrees off. However, in the conclusion we can read that:

The actual time to perform the cutting was O(k), therefore (again with a sufficiently large choice of c) the amortized running time is constant.

Where it is amortized to constant time? How? I don't understand, why it turns out to be constant, if I can see a linear dependency: the number of cut-off trees may be dependent on the height of the tree.

0

There are 0 best solutions below