Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
If this is an implementation detail of an actual program (as opposed to a homework problem), if the stack grows very often, you might consider increasing the size by a constant factor instead of by 4. – marty cohen Sep 28 '11 at 19:05
@marty yeah it's a constraint. If I was programming this I would probably increase it by much more than 4 :) – n0pe Sep 28 '11 at 19:24
up vote 3 down vote accepted

It appears that the formula you want is $$f(i)=4i-3$$ where $i$ is the number on the left.

I don't really know anything about what a stack is, but working from your description, this formula can be seen to be correct because it is correct for $i=1$, and then every time $i$ is increased to $i+1$, the size of the corresponding value should be increased by 4, which is captured by $$f(i+1)=4(i+1)-3=(4i-3)+4=f(i)+4$$

share|cite|improve this answer
As for why this is plausible: note that if you take successive differences of the original data, you get a constant difference of 4 (i.e. the the $n$-th term is always four more than the one before it); the $-3$ part you can get by figuring out what value of $k$ in $4n+k$ is needed so that the expression is equal to $1$ for $n=1$. – J. M. Sep 28 '11 at 17:16
Thanks @J.M. and thank you Zev! – n0pe Sep 28 '11 at 17:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.