Tag Info

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. ...

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 ...

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 ...

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