Whiteboard: Analysis of Doubling Strategy for Dynamic Arrays скачать в хорошем качестве

Whiteboard: Analysis of Doubling Strategy for Dynamic Arrays

The Whiteboard videos consist of short explanations that I would typically give at the whiteboard. This is the whiteboard deriving that the amortized running time of a push/append for a dynamic array is Theta(1) if we use the doubling strategy, i.e., if we double the size each time we run out of space. small errata: "In order to determine the biggest i in the series of 2^I * c terms, we need to look for an i such that 2^i * c く n ≤ 2^(i+1) * c. This leads to i = ceil( log(n/c) ) - 1" (and not as I wrote in the second line floor( log(n/c) ) ). Thanks to Gerhard Rupert for pointing this out. The remaining argument can remain the same since we are taking an upper bound and ceil( log(n/c) ) - 1 ≤ floor( log(n/c) ) ).