# Tag Info

Accepted

### Incremental strongly connected components

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

### Amortized time cost of insertion into an Array list

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)$ ...
• 270k
Accepted

### What is the intuition behind the Potential Function in Amortized Analysis of some algorithm?

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

### Why is a sequence of n Push, Pop, Multipop operations O(n²)?

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. ...
• 6,998
Accepted

### Complexity of many constant time steps with occasional logarithmic steps

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.
• 270k
Accepted

### How can I make sense of amortized accounting method?

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 ...
• 9,219
Accepted

### Does amortized complexity always equal to worst case complexity divided by n?

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))$...
• 270k
Accepted

• 270k

### Finding potential function for dynamic array

When $t(n)=n+1$ it's the case when the array is full and we need to double the size of our array, so: As you mentioned our potential function is $\phi(n) = 2n - m$, but now the array size doubled, ...
• 181
Accepted

### The Potential function for Fibonacci heaps

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 ...
• 71.1k

### What does $O(\alpha(n))$ amortized time mean?

$\alpha(n)$ is the inverse Ackerman function.
• 143k

• 251