How do you prove the following is a bad idea?

[iamsmooth]

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).

[iamsmooth]

Oh, I think I know the worst case. You have to consider expandStack() which expands the array by 2 times when the size of stack is the same as array. So at stack size 32, and array size of 32, when we push an object into the stack, the method finds that the stack is equal to array size so it is multiplied to 64. Immediately after, we pop an object out which means it is no longer 1/2 of the array again so immediately it contracts it again. Whereas if it only contracted it when it was 1/4, this would not happen.

This should cause extra usage in the time of the algorithm. However, I don't know how to convey this on paper with asymptotic notation :( Hmm...

[BestJewSinceJC]

Just some thoughts. .

1) because with the 1/2 condition, if you downsize the array, it will be much more likely that you will then have to subsequently resize the array later (due to having more elements than can fit in the new array you created in contractStack).
2) You should also consider that if you downsize the array based on the < 1/2 condition, then you will be resizing the array more often than you would be with the < 1/4 condition.

[Rashakil Fol]

This should cause extra usage in the time of the algorithm. However, I don't know how to convey this on paper with asymptotic notation :( Hmm...

You would just write that each push and pop wolud take Theta(n) time. (And so the average time per operation is Theta(n) which is bad because we'd like it to be O(1).)

[iamsmooth]

Why is it Theta(n)? Isn't it still O(1) since it's still a constant number of steps done twice? Or does the fact that it's repeated mean it's linear where n is the amount of repeated operations?

[Rashakil Fol]

Why is it Theta(n)? Isn't it still O(1) since it's still a constant number of steps done twice? Or does the fact that it's repeated mean it's linear where n is the amount of repeated operations?

No, when n is the size of the array, resizing takes Theta(n) time because you have to copy all the elements.

[iamsmooth]

"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^2 steps"

Okay, I understand how it would be Theta(n) if it was to resize on 1/2 needlessly when it could be a constant number of steps without the resize. But what does it mean when it says cn^2, does that imply it's somehow quadratic? I've talked to my other classmates and we all agree it's linear but don't understand how it's n^2.

How do I use cn^2 as opposed to cn?

[Rashakil Fol]

When you run a Theta(n) operation n times, it takes Theta(n^2) time to do. I mean in general if you run an operation that takes n seconds n times, it's going to take n*n seconds.

[iamsmooth]

Okay, that makes a lot more sense. I thought the notation could only cover the method itself, not extending to the desired user actions (i.e. repeatedly using an algorithm in a sequence).

Thanks a lot for the help, really really appreciate it.