New answers tagged

0 votes

Amortized Analysis of extract-min-operation of Fibonacci Heap

As D(n) denotes the max degree of any node, the highest degree of any child of the deleted node can be D(n)-1, and there can be at most D(n) children of the deleted node. Now after merging all the ...
user avatar
0 votes

Amortized analysis on a dynamic table that grows its size by $\sqrt{size} $

You can't use the physicists' or accountants' method, as these are only applicable for proving an upper boundon the amortized cost, and you need a lower bound. Consider the time it takes to double in ...
user avatar
  • 3,200

Top 50 recent answers are included