The question (in a nutshell) is this. I have an array which is an implementation of a stack. The array starts off with a size of 4 and every time it overflows (the user pushes a value when the array is full), a new array of size N + 4 is created and the old values are pushed in to the new array.m Every time the user pushes a value which creates a new array, this is called a special push.
I'm looking for a way to express the cost (in pushes) of the i th special push.
I made a table showing the number of the special push (i) and the amount of pushes they cost respectively:
1 1 2 5 3 9 4 13 5 17 6 21 7 25 8 29
Basically, I need to find a relation between the first column and the second. If I subtract the value in the second column with the value in the first I get that the differences start at 0 and increment by 3 each time. Therefore I have:
$ x - i = 0,3,6,9,12,15,... $
Where x is the cost of the ith special push.
How can I express this? Am I over-complicating things?