Questions tagged [dynamic-array]
The dynamic-array tag has no usage guidance.
5
questions
3
votes
2
answers
752
views
Amortized analysis on a dynamic table that grows its size by $\sqrt{size} $
The following problem is based on the section about dynamic table as part of the discussion about amortized analysis in CLRS
Problem: We are given a dynamic table $T$ that supports INSERT operation, ...
- 233
1
vote
0
answers
72
views
Finding the total work of an array list expansion effort
Suppose we are given an array-based list data structure. Suppose that its initial capacity is
$m > 0.$ When appending an element to the end of the list, if the list is full, we extend its capacity ...
- 52
1
vote
1
answer
174
views
Aggregate method for dynamic table (amortized analysis)
For amortized analysis (aggregate method), dynamic table insertion cost can be divided into:
if no expansion, then cost = 1
if we expand the table, then cost = i (if i-1 is an exact power of 2)
then ...
- 123
0
votes
2
answers
52
views
Big O of dynamic array
Skiena's Algorithm Design Manual, 3rd Ed p.71 gives the time complexity of a dynamic array according to the number of movements, $M$, as:
$$
M = n + \sum_{i=1}^{lg(n)} 2^{i-1} = 1 +2+ 4+\ldots+\frac{n}...
- 113
0
votes
1
answer
87
views
Prove with potential method that dynamic table with $q > 1$ expansion runs in amortized constant time
Suppose I have a dynamic table supporting $Insert$ procedure, which sets an input value after the tail of the dynamic table. If the underlying table is already full, we multiply its size by $q > 1$....
- 52