Questions tagged [amortized-analysis]
The amortized-analysis tag has no usage guidance.
12 questions
24
votes
0
answers
523
views
Can we do integer addition in linear time?
Why, yes, of course. But I'm actually interested in the cost of computing the sum of multiple integers:
Input: A sequence of nonnegative integers $\langle X_i:i<k\rangle$ written in binary.
Output: ...
- 18.6k
1
vote
1
answer
68
views
Indexed access with deletion
As part of a larger data structure that I am working on, I have the following sub-problem:
I start with $n$ slots in an array. Initially all slots are valid. I want to support two operations:
...
- 61
0
votes
0
answers
76
views
Frogs Game Amortized Analysis
The game is defined by two integer parameters: n and k.
We are given an array of n sets:
$$S_1, S_2, ...., S_n$$
such that, each of them is a subset of
$\{1, 2, ..., k\}$.
Adversary picks a set $S_i$ ...
- 21
4
votes
0
answers
77
views
When was the dynamic array first used as an example for amortized analysis?
I'm writing a report on amortized analysis, and I'm using the example of a dynamic array to explain each method. I think it would be nice to add a reference to when this example was first used, as it ...
- 41
3
votes
2
answers
482
views
Examples/Textbooks on amortized analysis of algorithms
I am trying to get the amortized analysis for a complicated algorithm. I am wondering whether there are textbooks or illustrative examples that could serve as inspiration of techniques in amortized ...
- 1,163
9
votes
0
answers
220
views
References for de-amortization
I've been interested in looking into the area of de-amortization recently (i.e. finding data structures with matching worst-case and amortized running time bounds, or exhibiting lower bounds against ...
- 525
1
vote
0
answers
57
views
What should I read to learn about the different models of computation used in algorithm and especially data structure analysis?
Are there any good surveys? Courses? Lecture notes?
I'm especially interested in material with practice exercises, if any is available.
Thanks!
- 141
18
votes
1
answer
2k
views
Splay tree potential function: why sum the logs of the sizes?
I'm teaching a course on data structures and will be covering splay trees early next week. I've read the paper on splay trees many times and am familiar with the analysis and intuition behind the data ...
- 2,262
6
votes
2
answers
386
views
Maintaining the product of a queue of semigroup elements
I have a queue $Q$ where elements can be popped from the left and added to the right in $O(1)$ time. The elements are members of a fixed semigroup $S$ with $O(1)$ time multiplication. Let the ...
- 3,313
2
votes
1
answer
1k
views
Amortized Analysis - Potential Method
I read about Potential Method when I was trying to understand some calculations.
I just can't understand how do you perform the calculation it self. How can you even define $O(n)-O(n)$ as it is used ...
- 133
-1
votes
1
answer
370
views
Amortized Analysis [closed]
I have two questions.
My book: "We must ensure that the total amortized cost of a sequence of operations provides an upper bound on the total actual cost of the sequence. This must hold for all ...
Guestt
13
votes
0
answers
377
views
Applications of an access lemma for dynamic forests?
Sleator and Tarjan's amortized analysis of splay trees builds on their so-called Access Lemma. For purposes of analysis, assign an arbitrary weight to each node $v$, and let $size(v)$ denote the sum ...
- 23.3k