Does array always have a wasted space of 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).