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


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


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.


7

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

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

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

Consider a data structure with operations $o_1,\ldots,o_k$. We say that these operations have amortized time $t_1,\ldots,t_k$ if any sequence of operations which contains $m_i$ operations of type $o_i$ runs in time at most $\sum_i m_i t_i$. This is essentially the same definition as yours, in a more general setting. We often allow $t_1,\ldots,t_m$ to depend ...


4

As phan801 commented, the first interpretation, a sequence of $n$ operations, each of which is either push or pop or multipop, is correct. Either one of the other two interpretations might stand a small chance without surrounding context or with a very different context. However, had it been the intended meaning, "the phrase would probably have a ...


3

Let's review the potential function method. Suppose that the $i$th operation costs $c_i$ and the value of the potential function at time $i$ is $\Phi_i \geq 0$, and that $\Phi_0 = 0$ (the potential at the beginning). Define the amortized operation costs by $a_i = c_i + \Phi_i - \Phi_{i-1}$. Then $$ \sum_{i=1}^n a_i = \sum_{i=1}^n (c_i + \Phi_i - \Phi_{i-1}) =...


3

I'll just answer a) and b) because I don't know the potential method. About a) Worst case analysis only considers a single operation. If you want to know how expensive your algorithm is in its worst case, you need to find the worst case cost of every single operation and then count how often each of them is executed. For example, you may have come about a ...


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

First, for a bit of clarifying terminology: rather than proving an amortized insertion cost of $O(\lg n)$ and an amortized deletion cost of $O(1)$, you are using those amortized costs to prove something about the total cost of a sequence of insertions and deletions, starting with an empty heap. This might be a subtle distinction, but it is fairly important ...


3

Here is a solution using direct calculation (I never liked all the fancy methods). Consider the cost of the first $n$ inserts, and suppose that $2^k \leq n < 2^{k+1}$. Thus only the arrays $A_0,\ldots,A_k$ are active. The cost of the $m$th operation can be broken down as follows: Creating the initial array: 1. If the number of elements (before adding the ...


3

Because it works. In amortized analysis, you pick the potential function. While it's usually related to some insight about the data structure or algorithm work, is it per se completely arbitrary. The only important thing is that if you write down the telescoping sum -- which is always set up in the same way! -- you can derive a good estimate.


3

This approach suggest to pick any constant factor $k>1$ and use that whenever one needs to reallocate the array. That is, each time the array becomes full and has $n$ elements, a new array of size $k\cdot n$ is allocated, and data is copied from the old array. It is important here to multiply the size by a constant $k$ rather than, say, adding a fixed ...


3

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


2

At every index of the array you should store an extra detail of the immediate index that contains a "0". Updating this index in an amortised complexity of O(1) will give the solution. Suppose you are updating the extra detail at an index i and the immediate 0 is found at j. Then, the extra detail will have the value j for all the values between i & j. ...


2

Amortized is not just probabilistic, it means that for some big enough $y$, $xy$ operations can't take a long time and will guaranteed to be $O(x)$ in average in worst case (and therefore $O(xy)$ for all $xy$ operations), even through some of operations may take even $O(xy)$ time itself. https://stackoverflow.com/questions/200384/constant-amortized-time


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