13
How to come up with sum-of-logs potential
Let's consider the BST algorithm $A$ that for each access for element $x$, it rearranges only elements in the search path $P$ of $x$ called before-path, into some tree called after-tree. For any element $a$, let $s(a)$ and $s'(a)$ be the size of subtree rooted at $a$ before and after the rearrangement respectively. ...
7
A queue can be represented as two stacks and be maintained in amortized constant time. It's then easy to maintain product of all elements of a stack.
See Purely Functional Data Structures by Chris Okasaki. (More specifically, figure 3.2 on pp. 18. )
About how to maintain on stacks:
Suppose the stack is $s_1, s_2,\ldots, s_n$ from bottom to top. For one ...
1
You may be interested in the classic papers by Robert Tarjan and others:
"The Amortized Computational Complexity" by Robert Tarjan on a survey of amortized analysis of several algorithms and data structures.
"Amortized Efficiency Of List Update and Paging Rules" by Daniel Sleator and Robert Tarjan on self-organizing lists.
"Self-Adjusting Binary Search ...
1
For textbook references an interesting article is as follows:
https://www.geeksforgeeks.org/analysis-algorithm-set-5-amortized-analysis-introduction/
I can also refer to one recent paper which is very simple involving a straightforward application of amortized analysis:
https://arxiv.org/abs/1804.01823
Only top voted, non community-wiki answers of a minimum length are eligible
Related Tags
amortized-analysis × 9ds.data-structures × 5
reference-request × 3
ds.algorithms × 2
lower-bounds × 1
big-list × 1
tree × 1
research-practice × 1
online-algorithms × 1
dynamic-algorithms × 1
intuition × 1
program-analysis × 1
worst-case × 1