# 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

## 1 Answer

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