# Questions tagged [dynamic-array]

The tag has no usage guidance.

5 questions
Filter by
Sorted by
Tagged with
83 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$....
1 vote
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 ...
1 vote
161 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
51 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
### 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, ...