Questions tagged [dynamic-array]
The dynamic-array tag has no summary.
7 questions
0
votes
1
answer
104
views
Why are dynamic arrays called ArrayLists in Java?
The point of Java's ArrayLists is that they adjust their length automatically whenever items are inserted or deleted. If I understand it correctly, ArrayLists are wrappers around primitive arrays.
I ...
- 103
1
vote
3
answers
187
views
Can there exist a deque like data structure that supports amortized $O(1)$ random access?
A lot of modern languages usually have a "list" or "vector" structure which allows for amortized $O(1)$ append and removal from back as well as amortized $O(1)$ random access.
I'm ...
- 375
0
votes
1
answer
155
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$....
- 60
1
vote
0
answers
97
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 ...
- 60
1
vote
1
answer
242
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
102
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
3
votes
2
answers
1k
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, ...
- 243