# Tag Info

29

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

14

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

13

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 $... 13 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, ... 12 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 analysis uses the potential function $$\Phi(F)=|W| +2\cdot \text{# marks}.$$ If we call ExtractMin this might cost$O(\left|W\right|)$, however after the ... 12 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 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$... 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 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 "... 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. 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 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 ... 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 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 ... 4 \alpha indicates the Inverse Ackermann Function: \alpha(n) is the number such that A(\alpha(n), \alpha(n)) = n. In practice, \alpha(n) \lt 5 for any input less than about ^72. So O(\alpha(n)) is basically O(1). The difference only matters in theory, never really in practice. You'll find O(\alpha(n)) mostly when working with disjoint sets, ... 4 Asymptotically, you're right: for big-enough inputs, the \Theta(n\log n) algorithm can be faster. However, this is only true for big enough n. It might be that "big enough" means "far bigger than any actual computer can store" or even just "plenty bigger than any input I care about". For a specific example of this, look at matrix multiplication ... 4 You have caught an instance of the infamous off-by-one error in that popular textbook whose name we shall not mention again. To repeat, it is correct that "the cost c_1=1, \Phi_0=0", "num_1=size_1=1 \implies \Phi_1 = 2\cdot1-1 =1" and " \hat{c_1}= c_1+\Phi_1-\Phi_0 =2". It is incorrect to state that \widehat c_i=... 3 The two are not mutually exclusive. In most situations you're interested in amortized analysis, since usually operations are fast enough so that no user would notice a one time long running time, the real performance being determined by the amortized running time. A good example is garbage collection, essential to many modern computer languages. Garbage ... 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$$ \... 3$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 ... 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

Amortized analysis deals with the runtime cost of an operation as an average over a sequence of operations. This is similar to the financial concept of amortization -- a single lump sum, such as a loan, is amortized over a period of time. This fixes a monthly payment for example, even though the principal balance is growing smaller. In this way, an ...

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