If I allowed to use space linear in the number of items in the array, can I use the above array? If so, how is 2N-2 considered linear in the number of items?

Prasanna Raman wrote:I am having trouble understanding space usage. Suppose I create a stack using a re-sizing array - an array that doubles itself when the stack is full; at any point, the maximum space usage is (2 * number of items) - 2.

I think your idea of "number of items" must be different from mine. An element isn't part of your

`Stack`

*until*you've resized the array (if it's full)

__and__copied the previous contents

__and__added the new element in the correct place.

Is this usage proportional to the number of items in the array?

What do you think? I reckon the more relevant question is: is it

__directly__proportional to the number of items in the array?

If I allowed to use space linear in the number of items in the array, can I use the above array?

The above array or the above

*formula*? You can resize an array any way you like, and at any time you like.

If so, how is 2N-2 considered linear in the number of items?

It isn't. However, it makes adds work in "

__amortized__constant time" (if that's what you mean by 'linear'). I'm afraid that the explanation for

*that*is a bit involved though; if you're really interested in how it works, check here.

I think maybe you need to try to boil this down to a single question: what

*exactly*is it that's puzzling you?

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

http://coursera.cs.princeton.edu/algs4/assignments/queues.html

`Your randomized queue implementation must support each randomized queue operation (besides creating an iterator) in constant amortized time and use space proportional to the number of items currently in the queue.`

I think I understand what amortized means. If there are a large of operations, some operations may take more time than the others, but if you take the average time of the operations, it is within bounds. My question is here is about the 2nd part - use space proportional to the number of items currently in the queue.

What is meant by the "proportional to the number of items currently in the queue"?

Prasanna Raman wrote:What is meant by the "proportional to the number of items currently in the queue"?

Personally, I think it's badly worded. I suppose having an array that is resized by doubling still means that it's "proportional" to the number of elements since, at the point of resizing (assuming you only resize when you've run out of room), it will be equal to

`2n`, so if

`s`is the size of the array, then

`n <= s <= 2n`.

However, IMO, the word "proportional" is rather vague. To me

`n:kn`is a very

*different*proportion to

`n:n+k`(where

`k`is a constant), but it's the

*first*one that gives you the amortized constant time.

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here