Dynamic Arrays and Amortized Analysis

Question 1

Dynamic array in c++, c#

Answer 1

uses vector, list

Question 2

difference between array and dynamic array is

Answer 2

resizable

Question 3

the operation time of appending a new element to a dynamic array is

Answer 3

often o(1), but o(n) only if resize need

Question 4

resizing happens by

Answer 4

factor of two. (some space can be wasted)

Question 5

Amortized Analysis : the definition of aggregate method is

Answer 5

the cost of n operations divided by n.

Question 6

Amortized Analysis : the definition of Banker’s method is

Answer 6

Charge extra for each cheap operation and save the extra charge as tokens to pay for expensive operations.