# amortized analysis

I am trying to find a general solution for the given A,B,C in dynamic arrays. Those veriables presents factors in the following operations :

given :

• c_i the size of the array after operation O_i (c_0 := 0)

• s_i is the number of elements after operation O_i (s_0 := 0)

• c_i ≥ s_i

after pushBack: if s_i−1 = c_i , then c_i = A · s_i.

after popBack: if s_i−1 ≤ c_i−1/B , then c_i = C · s_i.

• (pushBack and popBack are operations in a dynamic arrays ).

• (s_i = size, c_i = capacity )

how can i find values for A , B and C (in dependence of f) , with for a given f with 0 < f < 1 and A , B, C with A > 1 and B > C > 1 , so that s_i ≥ f·c_i ?

Note :

it would be nice to add a little explanation of how the results are found, it's very important to me to understand it.

• The question is somewhat poorly formulated. While it can be followed with some difficulty, it is better if you reformulated it for the benefit of readers who aren't aware of dynamically resizing arrays. Jun 12 '17 at 21:43
• @YuvalFilmus thanks for the note , should i add some links which explain the dynamical arrays ? Jun 12 '17 at 22:59
• I'm afraid that won't be enough. Try to reformat your question to make it look like other questions. Jun 13 '17 at 5:03