I have a class that creates a stack object implemented with an array:

So I have a method contractStack() which is called when the length of an array of the same class is greater than INITIAL_CAPACITY of 8, and the size of the stack (contents within the array) is less than or equal to one-quarter of the array's length.

i.e. top <= (Array.length / 4)

Now, I have to prove that it is a bad idea to call this method when the size is less than one-half instead of one-quarter of the array's length.

i.e. top <= (Array.length /2)

The instructions say:

"In order to see this is a bad idea, show the worst case amortized cost of a sequence of n operations on the stack would be Big Omega(n) instead of O(1), if contractStack was used like this.

You should do this by finding some constant c that is greater than 0 and proving that for every inter n >= N0 = 32, there is a sequence of n operations on a stack (following the use of the constructor to initialize it as an empty stack) whose execution requires at least cn^e steps"

I understand the question, but I don't understand how the cost of the operations would be more expensive. Anyone have a good guess at what i'm supposed to do?

My implementation of contractStack is:

```
private void contractStack () {
int[] tempArray = new int[(StackContents.length /2)]; // creates new array of half size
for (int i = 0; i <= top; i++) {
tempArray[i] = StackContents[i]; // places contents of stack into new array
}
StackContents = tempArray; // Set StackContents to the new smaller array.
}
```

I have found bounds for this operation in the function: 3n + 4, which means there are 3 units of cost in the loop, and 4 constant units for the method in general. Which means the worst case cost of this function should be Theta(n).

*Edited
by iamsmooth*: n/a