0
$\begingroup$

In this question it's stated that dynamic array wasted space is O(n). Here is the explanation why:

Because, when a dynamic array is full, its size is increased by some factor α. This means that, immediately after growing, a dynamic array holding n items has size about nαnα, so the amount of wasted space is n(α−1)=O(n)n(α−1)=O(n).

I'm wondering if it's always O(n). Maybe there is some logic similar to this one which proves that wasted space is not O(n)?

$\endgroup$
  • $\begingroup$ How do you want to define "wasted space"? In particular? Worst case or average case? Amortised? $\endgroup$ – Raphael May 8 '17 at 22:31
  • $\begingroup$ You can use virtual memory which eliminates the memory waste upon array resize, so no $\endgroup$ – JarkkoL May 9 '17 at 3:52
1
$\begingroup$

It depends on the algorithm used. Someone made the assumption that when an array has space for n items, and the n+1st item needs to be added, the array would be resized to a size c·n for some constant c > 1. But there is nothing forcing us to do this; we could resize from n items to f (n) items, where f (n) ≥ n+1 obviously but f (n) - n = o (n).

$\endgroup$

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.