Win a copy of OCP Java SE 8 Programmer II Exam Study Guide this week in the OCP forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Understanding space usage

Ranch Hand
Posts: 422
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. Is this usage 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? If so, how is 2N-2 considered linear in the number of items?

Ranch Hand
Posts: 426
You may not have taken into account the fill factor or load factor.

Bartender
Posts: 10575
66

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

Prasanna Raman
Ranch Hand
Posts: 422
Thank you, Winston. Here's the source of my problem:

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"?

Winston Gutkowski
Bartender
Posts: 10575
66

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