All Questions
Tagged with amortized-analysis ds.data-structures
6 questions
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
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
-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