Questions tagged [amortized-analysis]
A method in analysis of algorithms that considers the overall cost of a sequence of operations.
18
questions
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
50
votes
9
answers
16k
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,036
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 ...
- 791
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
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
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,214
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
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
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
3
votes
1
answer
167
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
2
votes
1
answer
627
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
0
answers
106
views
Array counter with mimimum find
I need to implement data strucure such as array, but with the following interface:
GetMin() - Returns the minimum from the array
IncRight(index) - Increases all values from specified index to the end ...
- 49
1
vote
1
answer
2k
views
How to do amortized analysis for an expanding array? [duplicate]
If you have an array that expands when it is completely filled and the new size is
N = N + 1 + ceiling(log2(N)) (N is the current size, and then N becomes the new ...
- 553
0
votes
1
answer
1k
views
Binary counter amortized analysis [closed]
This is a question I have stumbled upon in my textbook, and didn't really know how to approach:
Given a $k$-bit binary counter.
We have an operation Increment, which adds 1 to the counter.
We add a ...
- 429
-1
votes
1
answer
332
views
Custom binary counter supports only increment in $2^i$ values amortized analysis
I'm a having trouble analyzing this algorithm.
This is a binary counter that supports only increments in $2^i$ values
it's implemented in this way:
starting from the $i$-th location change all the ...
