Questions tagged [amortized-analysis]
A method in analysis of algorithms that considers the overall cost of a sequence of operations.
142
questions
50
votes
9
answers
15k
views
Does there exist a priority queue with $O(1)$ extracts?
There are a great many data structures that implement the priority-queue interface:
Insert: insert an element into the structure
Get-Min: return the smallest element in the structure
Extract-Min: ...
- 9,006
30
votes
2
answers
30k
views
Why is push_back in C++ vectors constant amortized?
I am learning C++ and noticed that the running time for the push_back function for vectors is constant "amortized." The documentation further notes that "If a reallocation happens, the reallocation is ...
- 1,587
27
votes
2
answers
6k
views
Data structure with search, insert and delete in amortised time $O(1)$?
Is there a data structure to maintain an ordered list that supports the following operations in $O(1)$ amortized time?
GetElement(k): Return the $k$th element of the list.
InsertAfter(x,y): Insert ...
- 968
12
votes
1
answer
8k
views
Potential function binary heap extract max O(1)
I need help figuring the potential function for a max heap so that extract max is completed in $O(1)$ amortised time. I should add that I do not have a good understanding of the potential method.
I ...
- 223
11
votes
1
answer
1k
views
Incremental strongly connected components
For a changing directed graph, I would like to maintain information about strongly connected components. The graph operations are incremental: only vertex addition and edge addition. What data ...
- 2,164
11
votes
1
answer
445
views
Can an NP-hard problem be polynomial on average?
I'm wondering if there are any $NP$-hard problems which are ``polynomial" in the average case. I think there are two ways to interpret this?
If $P \neq NP$, can there be an algorithm solving an $NP$-...
- 29.5k
8
votes
4
answers
2k
views
Questions about amortised analysis
As a preperation of an exam about algorithms and complexity, I am currently solving old exercises. One concept I have already been struggling with when I encountered it for the first time is the ...
- 235
8
votes
1
answer
7k
views
What is the intuition behind the Potential Function in Amortized Analysis of some algorithm?
I have come across many amortized analysis using a potential function. They all look magical to me. Everything works perfectly but I never got the intuition behind how they come up with such a "...
- 83
8
votes
0
answers
2k
views
Choosing potential function in amortized analysis
How should I think to choose the potential function in the amortized analysis?
More specifically are there techniques or tips for choosing optimal or good potential functions?
- 81
7
votes
1
answer
4k
views
What is the purpose of Mark field in Fibonacci Heaps?
In Fibonacci heaps, we keep a mark field for every node in the heap. Initially all the nodes are unmarked. Once a node is deleted, its parent is marked. If a node is deleted and its parent is already ...
- 541
7
votes
1
answer
6k
views
Amortized time cost of insertion into an Array list
A dynamically resizing array list will resize when the number of elements reaches a power of two. So, after n elements inserted, we've resized at sizes 1, 2, 4, ... , n. This also means we've copied ...
- 197
7
votes
1
answer
4k
views
How can I make sense of amortized accounting method?
Amortized accounting method has to be one of the most abstract analysis technique I have ever seen in my life (maybe aside from the potential method which I haven't read).
In the example of the Stack ...
- 781
7
votes
1
answer
437
views
Does this data structure already exist?
I was working on a problem for some time now, and I made a data structure to solve it. To my surprise, I could not find any instance of this data structure on the internet (though I am certain someone ...
- 235
6
votes
2
answers
2k
views
Advantages of amortized analysis
I understood what amortized analysis does, but can anyone tell me what is the main purpose of this kind of analysis?
What I understood:
Let say we have 3 three operations a,b,c used 1,2 and 3 times ...
- 355
6
votes
1
answer
4k
views
Why is the path compression (no rank) for disjoint sets $O(\log n)$ amortized for Find-Set?
I was trying to understand why using only path compression (no rank) would yield $m log(n) $ total run time for a sequence of $m$ operations for Find-Set.
I was told that the potential function:
$$ \...
- 2,960
6
votes
1
answer
1k
views
Why do we need "potential” for amortized analysis?
In the current version as of the Wikipedia article “Potential method”, the amortized cost of each operation is defined as the following
$$
T_{\mathrm{amortized}}(o) = T_{\mathrm{actual}}(o) + C \cdot (...
- 269
6
votes
2
answers
803
views
Why isn't the time complexity of constructing a Fenwick tree tighter than $O(n\lg n)$?
Intuition:
Suppose I have an array of nonzero integer values $A[n]$ and a partially constructed Fenwick tree of this array: $F[k], n>k$. I can see why inserting the next element would be worst ...
- 301
6
votes
1
answer
97
views
Closest point in embedded simplicial complex
Suppose I have a simplicial $k$-complex $\mathcal S$ whose vertices are embedded in Euclidean space $\mathbb R^n$, for roughly $k< n\leq 6$. Examples include triangle mesh surfaces ($k=2$) embedded ...
- 161
6
votes
1
answer
2k
views
How to compute amoritized cost for a dynamic array?
I am trying to understand how to do the amortized cost for a dynamic table. Suppose we are using the accounting method.
Let A of size m be an array of n elements. When $n = m$, then we create a new ...
- 553
5
votes
1
answer
2k
views
What is a clairvoyant algorithm?
When talking about general data structure design, my lecture notes talk about one of the concerns being cost of operations. As well as the individual cost, it mentions amortized cost. But then it goes ...
- 153
5
votes
2
answers
2k
views
Finding potential function for dynamic array
About dynamic array, doubling it's size with every element that is beying its limit:
From what I understand, the number of operations between the $n$th element and the $n+1$th depending on if $n+1$ ...
- 209
5
votes
1
answer
993
views
Find amortized cost for insertion in binary arrays using accounting/potential methods?
Background:
The idea of this data structure is as follows. We will have a collection of arrays, where array $i$ has size $2^i$. Each array is either empty or full, and each is in sorted order. ...
Chia Phir
5
votes
0
answers
181
views
Prove: Self-organizing list that uses Move-to-Front is 2-Competitive
Preparing for my finals in my "advances algorithms" course. Usually there is a question to prove one of the theorems that was given over the course. I'm currently trying to write a full ...
- 223
4
votes
1
answer
3k
views
Why is a sequence of n Push, Pop, Multipop operations O(n²)?
From "Introduction to Algorithms" by Cormen, Leiserson, Rivest, Stein, Third Edition, page 453:
Let us analyze a sequence of $n$ Push, Pop, Multipop operations on an initially empty stack. The ...
- 143
4
votes
2
answers
3k
views
Does amortized complexity always equal to worst case complexity divided by n?
Is it true that given any operation that takes O(f(n)) amount of time, we do this n times in a process, then the amortized cost is O(f(n))/n?
I'm confused because this statement is so simple and ...
- 839
4
votes
1
answer
236
views
A formal definition for amortized time
Several (tutoring) students have asked me for a formal definition of amortized time and I've never been able to find one online. All the literature I've found usually outlines the three most common ...
4
votes
1
answer
5k
views
Amortised analysis of binary heap insert and delete-min
I'm trying to figure out how to do amortised analysis of heap insert and heap delete-min using potential function.
We can assume, that insert is O(logn) and delete-min is O(logn) too.
The goal is ...
- 329
4
votes
1
answer
2k
views
Basics of Amortised Analysis
I cannot really find a source that does not use the same examples provided by CLRS. I need a simpler example than MULTI-POP example. Could someone provide an ...
- 381
4
votes
1
answer
4k
views
Potential method for dynamic binary search
I'm trying to solve 17-2(b) problem from Cormen(CLRS) using potential method.
Problem from Cormen:
17-2 Making binary search dynamic
Binary search of a sorted array takes logarithmic search time, ...
- 285
3
votes
1
answer
516
views
Complexity of many constant time steps with occasional logarithmic steps
I have a data structure that can perform a task $T$ in constant time, $O(1)$. However, every $k$th invocation requires $O(\log{n})$, where $k$ is constant.
Is it possible for this task to ever take ...
- 203
3
votes
1
answer
8k
views
give potential function - binary heap - extract-min in amortized const time and insert in log amortized time
Consider an ordinary binary min-heap data structure with n elements supporting
the instructions INSERT and EXTRACT-MIN in O($\lg n)$ worst-case time. Give a
potential function $\Phi$ such that the ...
- 127
3
votes
1
answer
162
views
Where would someone find amortized analysis more useful than average analysis and the opposite?
I'm trying to understand the difference between these two. They both look at what happens on average, however amortized analysis is actually dealing with exactly the amount of operations you are doing ...
- 619
3
votes
2
answers
412
views
Amortized analysis on a dynamic table that grows its size by $\sqrt{size} $
The following problem is based on the section about dynamic table as part of the discussion about amortized analysis in CLRS
Problem: We are given a dynamic table $T$ that supports INSERT operation, ...
- 233
3
votes
1
answer
281
views
Amortised analysis of a simple loop and 3 operations
I'm trying to figure out amortised analysis of this loop and I can't figure out how to prove that complexity is $O(n \log n)$.
Operation OP(S,X[i]) has complexity ...
- 329
3
votes
1
answer
928
views
Amortized analysis of base Fibonacci counter
We just started learning the potential method this week and I'm having a bit of trouble on this problem regarding Fibonacci numbers; specifically I'm having some difficulty thinking of a good ...
- 133
3
votes
1
answer
105
views
When do you use amortized time complexity and when to use unamortized?
This is my guess:
-Use amortized because we want to know the "averaged" complexity over n operations assuming the ...
- 33
3
votes
0
answers
114
views
Formal justification of the accounting method and its meaning
I'm reading through CLRS again and I was wondering if there's a formal justification or construction of the accounting method, explaining why it works. For some reason it seems to me that CLRS ...
- 693
3
votes
0
answers
1k
views
Analysis of Weighted Quick Union with Path Compression
I have searched the internet for an analysis of why WQUPC is amortized $O( m \alpha (n) ) $ for m operations on n nodes ( $\alpha ( n) $ is the inverse Ackerman function).
I understand why it is $O ( ...
- 31
2
votes
2
answers
1k
views
What does $O(\alpha(n))$ amortized time mean?
DELETE(S, i): Delete integer $i$ from the set $S$. if $i \notin S$, there is no effect.
from a set of consectutive integers like $S = \{1,2,3,5,6\}$
Provide a data structure and an algorithm for ...
- 55
2
votes
2
answers
354
views
Constant factor of an array
In Elements of Programming Interviews in Python by Aziz, Lee and Prakash, they state on page 41:
Insertion into a full array can be handled by resizing, i.e.,
allocating a new array with ...
- 123
2
votes
3
answers
4k
views
Can an algorithm with $\Theta(n^2)$ run time be faster than an algorithm with $\Theta(n\log n)$ run time?
This is a question posted for extra practice (i.e., not for credit):
Can an algorithm with $\Theta(n^2)$ run time be faster than an algorithm with $\Theta(n\log n)$ run time? Explain.
I'm not sure ...
- 23
2
votes
1
answer
770
views
What is the amortized cost of pulling top K elements from a priority queue?
To pop an element off of a priority queue, the worst-case complexity is:
O(logN) where N is the number of elements.
Now if you do K pop operations on the priority ...
- 115
2
votes
2
answers
210
views
Designing a Data Structure that allows both insertion and extracting a number lower than median in amoritzed O(1) cost?
Consider a data structure that has only two functions. extract_lowerthan_median() and insert(). How can we design it in a way that the amortized cost for both the operation is O(1)?
Using a 2 tree, a ...
- 57
2
votes
1
answer
196
views
What is the meaning of the statement "a sequence of n PUSH, POP and MULTIPOP opreations"
I am reading CLRS 3rd Ed, chapter 17.1 (Aggregate analysis pg453) and I came across this statement.
Let us analyze a sequence of n PUSH, POP, and MULTIPOP operations on an initially
empty stack.
I ...
- 65
2
votes
1
answer
112
views
$\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
The following comes from section Dynamic Tables, Introduction to Algorithms by Cormen. et. al.
In the following pseudocode, we assume that $T$ is an object representing the table. The field $table[T]$...
- 1,042
2
votes
2
answers
2k
views
Sequence of N operations Amortized Analysis
A sequence of $N$ operations is performed on a certain data structure.
The $i$-th operation costs $i$ if $i$ is a power of 2, else it costs 1.
How can I calculate the amortized cost for every ...
- 429
2
votes
1
answer
101
views
Finding the Equation for Potential Method and Amortization Analysis
I am trying to figure out the solution to this problem:
In this problem we consider two stacks $A$ and $B$ manipulated using the
following operations ($n$ denotes the size of $A$ and $m$ the size of $...
- 23
2
votes
1
answer
611
views
The Potential function for Fibonacci heaps
I am trying to get a better understanding of Fibonacci Heaps. I noticed the
following definition for the potential function.
$$ \Phi(F)=|W| +2\cdot \text{# marks}. $$
I do not understand why it is ...
- 349
2
votes
1
answer
2k
views
Red-black tree amortized cost of the rebalancing
I've read in different sources that the amortized cost of a red-black tree rebalancing is constant (at least during the tree creation using only insertions).
How can it be proven?
- 143
2
votes
1
answer
170
views
Binary heap removal peculiar potential function analysis [closed]
Given the potential function $\phi$, it seems that remove max may take $O(1)$ amoratized,
meaning that $n$ removals would take $O(n)$, which can't be, as it means we get a linear time comparison based ...
- 506