0
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ How do you want to define "wasted space"? In particular? Worst case or average case? Amortised? $\endgroup$
    – Raphael
    Commented May 8, 2017 at 22:31
  • $\begingroup$ You can use virtual memory which eliminates the memory waste upon array resize, so no $\endgroup$
    – JarkkoL
    Commented May 9, 2017 at 3:52

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.