# Tag Info

Accepted

### Incremental strongly connected components

To the best of my knowledge, the best algorithm for decremental strongly connected components is presented in  with $O(m \sqrt{n} \log n)$ total expected update time.  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)$ ...
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. ...
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.
Accepted

Accepted

### Amortized analysis for doubling resizing array is ~3n

Note that the statement involves two variables $i$ and $n$. The sum of powers of two equals the next power minus one: $\sum_{k=0}^i 2^k = 2^{i+1}-1$. It is mentioned that $2^i$ is the largest power ...
### What does $O(\alpha(n))$ amortized time mean?
$\alpha(n)$ is the inverse Ackerman function.