14
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-...
- 166
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)$ ...
- 274k
9
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.
...
- 7,768
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.
- 274k
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(...
- 7,038
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 ...
- 9,027
5
votes
Accepted
Constant factor of an array
That's probably a typo or poor wording -- in the quote, "has" should be "is".
D.W.♦
- 154k
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$...
- 274k
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 ...
- 27.8k
4
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 ...
4
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 ...
- 274k
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 ...
- 274k
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 ...
- 4,421
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 ...
- 81.4k
4
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$", &...
- 38.5k
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 ...
- 38.5k
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 ...
- 71.9k
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, ...
- 181
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 ...
- 9,027
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,\...
- 274k
3
votes
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 ...
- 29.6k
3
votes
What does $O(\alpha(n))$ amortized time mean?
$\alpha(n)$ is the inverse Ackerman function.
D.W.♦
- 154k
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 $...
- 14.4k
3
votes
Accepted
Designing a Data Structure that allows both insertion and extracting a number lower than median in amoritzed O(1) cost?
Amassing many elements significantly lower than median at once
The basic idea is to maintain a list of small elements that are guaranteed to be lower than median. Also maintain a list of all other ...
- 38.5k
3
votes
Accepted
Finding the Equation for Potential Method and Amortization Analysis
Amortized analysis is a technique for showing how to distribute the total cost of a worst case sequence of operations among all the operations in the sequence to get an average cost. So even if there ...
- 2,590
2
votes
Amortised analysis of a simple loop and 3 operations
We can divide the running time into several parts:
Pushes.
Pops.
The first OP performed at every round.
Subsequent OPs performed at every round.
Note that every OP costs $O(\log n)$, that there are ...
- 274k
2
votes
Amortized analysis of base Fibonacci counter
As far as I know, there's no general method for designing a potential function, which makes sense when you consider that they can be used for different purposes. I've been trying on and off for 20 ...
- 21.3k
2
votes
Accepted
What does it mean when each individual array is sorted in different array but bear no relationship to each other
What they mean is exactly that: the invariant maintained by the data structure is that each of the arrays $A_0,\ldots,A_{k-1}$ is sorted. Nothing is maintained regarding the relative order of elements ...
- 274k
2
votes
Why does the total credit associated with a data structure must be nonnegative at all times for the accounting method?
The amortized analysis calculates complexity for a sequence of $ n \in \mathbb{N} $ operations, no matter how large $ n $ is and what is the structure of sequence (i.e. which operations are within the ...
- 166
2
votes
Question regarding the potential method for amortized analysis
In the potential method, operation $O$, which has real cost (say time complexity) $p(O)$ is charged $c(O)$. The potential at any given point is $$\sum_{t=1}^T (c(O_t) - p(O_t)),$$ where $O_1,\ldots,...
- 274k
Only top scored, non community-wiki answers of a minimum length are eligible