33

NO. Fredman and Saks proved that any data structure that supports these operations requires at least $\Omega(\log n/\log\log n)$ amortized time per operation. (This is reference [1] in the paper by Dietz that you mention in your first comment.) The lower bound holds in the very powerful cell probe model of computation, which only considers the number of ...


27

Our idea is to use threaded splay trees. Other than the Wikipedia article we will thread the trees so that every node has a pointer next to its successor in the in-order traversal; we also hold a pointer start to the smallest element in the tree. It is easy to see that extracting the smallest element is possible in (worst case) time $\mathcal{O}(1)$: just ...


24

The important word here is "amortized". Amortized analysis is an analysis technique that examines a sequence of $n$ operations. If the whole sequence runs in $T(n)$ time, then each operation in the sequence runs in $T(n)/n$. The idea is that while a few operations in the sequence might be costly, they can't happen often enough to weigh down the program. It's ...


20

Insert: $\mathcal{O}(\log n)$ Get-Min: $\mathcal{O}(1)$ Extract-Min: $\mathcal{O}(1)$ Amortized Time Simple implementations of a priority queue (e.g. any balanced BST, or the standard binary min-heap) can achieve these (amortized) running times by simply charging the cost of Extract-Min to insert, and maintaining a pointer to the minimum element. For ...


14

2-4 trees have amortized $O(1)$ modifications at known locations. That is to say, if you have a pointer to some location in the tree, you can remove or add an element there in $O(1)$ amortized time. You can thus just keep a pointer to the minimum element and the root node in a 2-4 tree. Inserts should go through the root node. Updating the pointer to the ...


12

Although @Marc has given (what I think is) an excellent analysis, some people might prefer to consider things from a slightly different angle. One is to consider a slightly different way of doing a reallocation. Instead of copying all the elements from the old storage to the new storage immediately, consider copying only one element at a time -- i.e., each ...


12

Try the following: The weight $w_i$ of an element $i$ in the heap $H$ is its depth in the corresponding binary tree. So the element in the root has weight zero, its two children have weight 1 and so on. The you define as potential function $$\Phi(H)=\sum_{i\in H}2 w_i.$$ Let us now analyze the heap operations. For insert you add a new element add depth $...


11

Amortised analysis is a tool to get more useful results than "naive" worst-case analysis. Especially in the realm of advanced data structures, operations can be cheap most of the time but expensive in rare cases; worst-cases analysis yields only the latter case as characteristic of the data structure. Dynamic arrays, splay trees and some flavors of hash ...


10

A clairvoyant algorithm is a (usually hypothetical) algorithm that can look into the future to guarantee that it makes the best possible decisions. The typical application is in so-called "online" problems, where the input must be processed as it arrives, before the whole input is known, or in other situations where an algorithm must act based on incomplete ...


10

It does change the complexity of the operations. Simply speaking, the root list $W$ gets too large. We have two expensive operations, which are ExtractMin and DecreaseKey. Remember that the amortized analyisis uses the potential function $$ \Phi(F)=|W| +2\cdot \text{# marks}. $$ If we call ExtractMin this might costs $O(|W|)$, however after the operation, ...


10

To the best of my knowledge, the best algorithm for decremental strongly connected components is presented in [1] with $O(m \sqrt{n} \log n)$ total expected update time. [1] Decremental Single-Source Reachability and Strongly Connected Components in Õ(m√n) Total Update Time - Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Jakub Łącki, ...


9

Consider the std::vector container from the STL, together with it's appending operation, push_back(). This operation has amortized running time $O(1)$. Why? std::vector implemented as an array which can dynamically grow, if more space is needed. The strategy it uses for resizing is simple: it doubles it's size whenever you try to push_back a new element to ...


8

By request, here is the structure I found after I formulated the question: The basic idea is to use a threaded Scapegoat tree along with a pointer to the minimum (and for good measure, the maximum as well). A simpler alternative to threading is maintaining predecessor and successor pointers in every node (which is equivalent, simpler, but has more overhead)....


8

First, let me comment on 2 misconceptions I see in your question: Landau notation ('Big $O$ notation') does not exclusively refer to running times, we can use it to describe any function we wish. The fact that the worst case running time is $O(n^2)$ doesn't mean the running time isn't also $O(n)$. The second part comes close to the point of this part in ...


8

If every $k$th operation takes $O(\log n)$ time, then the best bound you can get on the amortized complexity is $O(1 + \frac{\log n}{k})$. This follows from the definition of amortized complexity.


7

For the estimate, $$ n + \frac{n}{2} + \frac{n}{4} + \cdots +1 <n \left(1 + \frac{1}{2} + \frac{1}{4} + \cdots \right) = 2n, $$ since $1 + 1/2 + 1/4 + \cdots = 2$. If $n$ insertions take $O(n)$ time, then the amortized time per insertion is $O(n)/n = O(1)$. This is by the definition of amortized time. (More accurately, the amortized time is at most $K$ ...


6

Looks like the $\Omega(\dfrac{\log n}{\log\log n})$ barrier has been overcome by modifying the analysis from the chronogram technique. The new [lower] $\Omega(\log n)$ bound has been proved for similar problems in the cell-probe model [1]. From reading that article; it is my understanding that that bound applies to the list representation problem also. [1] ...


6

Imagine filling up a huge water tank. Now when you open the faucet you have nice water pressure. The pressure will last probably until the tank is almost empty (depending on its size). At that point you need to refill it to have your constant pressure again, so you make the effort again. The potential function is the water tank. You do some work that will "...


6

No, if all we know about an operation is that it takes $O(f(n))$ times, then its amortized time is also $O(f(n))$. Sometimes, however, it is the case that while the worst-case running time is $O(f(n))$, the worst case cannot happen all the time. A good example is dynamic arrays. Suppose we want to maintain an increasing array, but we don't know in advance ...


5

It would seem that the question has been answered at CSTheory.SE. Summary: it is, indeed possible. For example, the Max 2-CSP problem is NP hard with an $O(n)$ expected time algorithm. This makes sense, I guess. Sometimes only a small subset of instances is needed to make a problem $NP$-hard, like SAT vs 3SAT. But you can expand the problem, and as long ...


5

Let $a_i$ be the amortized costs of operation $i$, $c_i$ be the actual costs of operation $i$, and $D_i$ the data structure after operation $i$. The amortized costs of an operation are defined as $$a_i:=c_ i+ \Phi(D_i) -\Phi(D_{i-1}).$$ You usually assume the following The potential is always positive, that is $\forall\colon i \Phi(D_i)\ge 0$, In the ...


5

A quick note: the runtime is not guaranteed to be $O(m \log n)$. For example, suppose that your forest consists of $\sqrt{n}$ a linked lists, each of which has $\sqrt{n}$ nodes in it. Doing a total of $\sqrt{n}$ finds on the bottom nodes in each list will take time $\Theta(n)$, which means that the bound of $O(m \log n)$ (here, $O(\sqrt{n} \log n)$) is ...


5

That's probably a typo or poor wording -- in the quote, "has" should be "is".


4

The potential function method is complicated, your example is simple. The number of bits changed is 1 about half the time, 2 about a quarter of the time, 3 about an eighth of the time, and so on. This is because the number of bits changed, starting from 0, is 1,2,1,3,1,2,1,4 and so on (you get the pattern). So the average number of bits changed is $$ \sum_{k=...


4

$O(f(n))$ amortized time means that if we make $k$ consecutive operations, total time does not exceed $k \cdot cf(n)$ for a chosen positive constant $c>0$. In your case, each insertion is worst-case $O(\log n)$. However, they're amortized $O(1)$. It means that if you make $n$ consecutive insertions (that is, build a heap from an array), total time is ...


4

Amortized analysis is a strategy for analyzing a sequence of operations irrespective of the input to show that the average cost per operation is small, even though a single operation within the sequence might be expensive. As it is shown in the above quote, amortized analysis is applicable particularly to a sequence of operations in which cheap operations ...


4

As is unfortunately sometimes the case, Wikipedia is doing a terrible job of explaining what amortized analysis actually is. The idea of amortized analysis is that while operations may have a bad worst case cost, their average cost could be much lower. Average cost means different things in different circumstances. In amortized analysis, here is what it ...


4

The question might be a little misleading. So, after n elements inserted, we've resized at sizes 1, 2, 4, ... , n. This is only true if $n = 2^k$ for some $k \in \mathbb{N}$, because for a growth factor of 2, we only need to resize when $n$ is a power of 2. So in your case we would only resize at 1, 2, 4. Not 7. You should keep in mind this only ...


3

Amortized analysis relies on $\sum_{i=1}^n \overline{C_i} = \sum_{i=1}^n C_i+\phi_n-\phi_0$ being an upper bound for $\sum_{i=1}^n C_i$. This requires $\phi_n$ to be at least as large as $\phi_0$. Your potential function does not satisfy this requirement, aince $\phi$ will get smaller with each step.


3

How about this. Assume we maintain a binary counter $C$ that counts the operations executed so far. Let $D_i$ be the data structure after the $i$-th operation. We then define as potential $\Phi(D_i)$ number of $\tt 1$-digits in $C$. As usual $c_i$ denotes the actual costs, and $\hat c_i$ the amortized costs. If $i$ is not a power of two, then we have $$ \...


Only top voted, non community-wiki answers of a minimum length are eligible