Pergunta

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

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top