# Does array always have a wasted space of O(n)?

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

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