Questions tagged [dynamic-array]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
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$....
coderodde's user avatar
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 ...
coderodde's user avatar
1 vote
1 answer
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 ...
ryan chandra's user avatar
0 votes
2 answers
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}...
Lorem Ipsum's user avatar
3 votes
2 answers
693 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, ...
flamel12's user avatar
  • 233