• Post Reply Bookmark Topic Watch Topic
  • New Topic

Understanding space usage  RSS feed

 
Prasanna Raman
Ranch Hand
Posts: 410
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Roger Sterling
Ranch Hand
Posts: 426
Eclipse IDE Fedora Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You may not have taken into account the fill factor or load factor.
 
Winston Gutkowski
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 410
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!