0
$\begingroup$

I would like to discuss resizing strategies for arrays please. If you have an array of $k$ initial size and it gets full, so you would like to choose from one of the following approaches:

Approach 1: if array get full, then we resize the array by $k$ constant.
Approach 2: if array get full, then we resize the array by doubling the previous size.
Approach 3: if array get full, then we follow $3k, 5k, 7k, 9k, \cdots$ etc resizing.

Now to compare approaches:

  1. Approach 1 is time consuming as we do resizing more frequently.
  2. Approach 2 is memory consuming.
  3. Approach 3 is most intuitive one because it adopts to higher frequency of PUSH calls.

Problem: How approach 3 is more intuitive compared to approach 2 please? Both are similar as I see them.

$\endgroup$
3
$\begingroup$

Check amortized analysis. Note that usually array resizing requires (1) get memory for new version, (2) copy old contents over, (3) delete old version. The point of your approach 2 (double the size of the array each time, more generally extend by a fixed factor) is that it gives amortized constant cost for each push on the stack. The others get costlier when the stack grows.

$\endgroup$
2
  • $\begingroup$ Thank you very much. Very clear. But my question please is to why the solution I got above says that Approach 3 is most intuitive one because it adopts to higher frequency of PUSH calls? What does that mean? $\endgroup$
    – Avv
    Sep 16 '21 at 16:47
  • 1
    $\begingroup$ @Aura, the problem with approach 2 is that every so often the whole process grinds to a halt while stuff gets copied over (the individual cost of a push varies wildly). In any case, an individual push can be quite cheap (a few memory accesses) or very costly (need to extend --i.e., copy-- a huge stack). It very much matters what you want to prefer: if throughput use approach 2, if latency use some other --costlier on average, less variable cost-- data structure/algorithm. $\endgroup$
    – vonbrand
    Sep 16 '21 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.