Exercises 4. 3. 2021

From the lecture we know that we can implement flexible array with amortized complexity of append being \( \mathcal{O}(1) \).
We used doubling technique: Whenever the array becomes full, we double the capacity and realocate the array.

Ex. 1

What would happen if we increased the capacity by a different amount? Consider following schemes (\(C\) is the old capacity):
  1. \(C \rightarrow C + k\) where \(k\) is a constant (say 1 for starters)
  2. \(C \rightarrow C^2\)
  3. \(C \rightarrow 3\cdot C\), or generally \(C \rightarrow k\cdot C\) for some constant \(k > 1\)

Ex. 2

So far, new elements could be added only to the end of array. Is it possible to modify the array so that we can also add elements to the front? And what about deleting elements?