13 votes
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-...
user avatar
10 votes
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)$ ...
user avatar
8 votes
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 ...
user avatar
8 votes
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. ...
user avatar
  • 6,998
8 votes
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.
user avatar
7 votes
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 ...
user avatar
  • 9,219
6 votes
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))$...
user avatar
6 votes
Accepted

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

$\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(...
user avatar
  • 6,940
5 votes

Why is the path compression (no rank) for disjoint sets $O(\log n)$ amortized for Find-Set?

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 ...
user avatar
5 votes
Accepted

Can an NP-hard problem be polynomial on average?

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 ...
user avatar
  • 29.2k
5 votes
Accepted

Constant factor of an array

That's probably a typo or poor wording -- in the quote, "has" should be "is".
user avatar
  • 143k
5 votes
Accepted

A formal definition for amortized time

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$...
user avatar
5 votes

What is the amortized cost of pulling top K elements from a priority queue?

Big-O doesn't care about a factor 0.5, for example. Now log sqrt(N) = 1/2 log N. So if you take away enough elements to change the size of the queue from N to sqrt(N), you have multiplied the time by ...
user avatar
  • 25.6k
4 votes
Accepted

Why do we need "potential” for amortized analysis?

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 ...
user avatar
4 votes

Amortized time of insertion into an Array list

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 ...
user avatar
  • 4,371
4 votes
Accepted

Can an algorithm with $\Theta(n^2)$ run time be faster than an algorithm with $\Theta(n\log n)$ run time?

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 ...
user avatar
4 votes
Accepted

What is the meaning of the statement "a sequence of n PUSH, POP and MULTIPOP opreations"

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 ...
user avatar
  • 34.9k
3 votes
Accepted

Red-black tree amortized cost of the rebalancing

If you look at the rules for what happens in a red/black tree insertion, you can see that the fixup rules for maintaining the red/black invariants only propagate upward if the newly-inserted node ...
user avatar
3 votes
Accepted

Amortised analysis of binary heap insert and delete-min

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 ...
user avatar
3 votes
Accepted

give potential function - binary heap - extract-min in amortized const time and insert in log amortized time

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 ...
user avatar
3 votes
Accepted

Where would someone find amortized analysis more useful than average analysis and the opposite?

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 ...
user avatar
3 votes
Accepted

Creating a binomial heap from an array in Θ(n) time

$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-...
user avatar
  • 373
3 votes

Find amortized cost for insertion in binary arrays using accounting/potential methods?

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,\...
user avatar
3 votes

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, ...
user avatar
3 votes
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 ...
user avatar
  • 71.1k
3 votes

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

$\alpha(n)$ is the inverse Ackerman function.
user avatar
  • 143k
3 votes

Constant factor of an array

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 $...
user avatar
  • 14.2k
3 votes
Accepted

$\Phi_1=1$ or $\Phi_1=2$ for the dynamic $\text{Table-Insert}$ , where $\Phi_i$ is the potential function after $i$ th operation, as per CLRS

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$", &...
user avatar
  • 34.9k
2 votes
Accepted

If x operations cost O(x) amortized then how much xy operations cost?

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 ...
user avatar
  • 251
2 votes
Accepted

Amortized analysis of virtual, dynamic array using potential function

What am I doing wrong here? You're using the wrong potential function. Keep looking. If you want to know the solution, the Wikipedia page on the potential method contains the answer.
user avatar

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