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