Skip to main content
15 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-...
Alexander Svozil's 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)$ ...
Yuval Filmus's user avatar
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. ...
Discrete lizard's user avatar
  • 8,248
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.
Yuval Filmus's 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(...
Draconis's user avatar
  • 7,138
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.'s user avatar
  • 159k
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$...
Yuval Filmus's 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 ...
gnasher729's user avatar
  • 30.1k
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 ...
Algorithms with Attitude's user avatar
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 ...
Yuval Filmus's 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 ...
ryan's user avatar
  • 4,511
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 ...
David Richerby's user avatar
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$", &...
John L.'s user avatar
  • 39k
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 ...
John L.'s user avatar
  • 39k
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 ...
Raphael's user avatar
  • 72.4k
3 votes

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

$\alpha(n)$ is the inverse Ackerman function.
D.W.'s user avatar
  • 159k
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, ...
KaliTheGreat's user avatar
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,\...
Yuval Filmus's user avatar
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 $...
chi's user avatar
  • 14.6k
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 ...
John L.'s user avatar
  • 39k
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 ...
Russel's user avatar
  • 2,745
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 ...
Yuval Filmus's user avatar
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 ...
Pseudonym's user avatar
  • 22.1k
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 ...
Yuval Filmus's user avatar
2 votes

Is the potential difference in the two consecutive states of a data structure equal to the credit of the change inducing operation?

The potential function is a fictitious quantity which is used to bound the cost of operations in a data structure. Suppose that our data structure supports only one operation, whose worst-case cost is ...
Yuval Filmus's user avatar
2 votes

Finding potential function for dynamic array

You've already proved it! You said you were meant to bound it by $3n$ and you've bound it by $2n$. Well, $2n \leq 3n$, right?
Samuel Schlesinger's user avatar
2 votes
Accepted

Amortized analysis of resizing array implementation of a stack

They include the initialization of the new array. From page 207 of the text: Q. Does int[] a = new int[N] count as N array accesses (to initialize entries to 0)? A....
Tomoki's user avatar
  • 371
2 votes
Accepted

Height and depth of every node in Path Compression

I assume that the height of a node $\small x$, denoted as $\small h(x)$, is recursively defined as: $$ \small h(x) = \begin{cases} 0 & \text{ if $x$ is a leaf} \\ 1+\max\{h(y) \mid y\text{ is ...
PSPACEhard's user avatar
2 votes
Accepted

general question amortized cost and worst case

The answer hinges on the definition of amortized cost. Since you haven't given such a definition, let me assume that you are using the common definition. Consider a data structure supporting ...
Yuval Filmus's user avatar
2 votes
Accepted

Best known (state of science) time complexity of an array access problem

Ok so I think you can build a structure that has $O(1)$ (amortized) complexity for all operations, and using $O(n)$ space for $n$ insertions. The underlying array is a dynamic array (let's call it $T$...
GBathie's user avatar
  • 632

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