Questions tagged [amortized-analysis]
A method in analysis of algorithms that considers the overall cost of a sequence of operations.
43
questions with no upvoted or accepted answers
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
5
votes
0
answers
222
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
3
votes
0
answers
117
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 ...
- 703
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
0
answers
117
views
Difficulty in last sentence in proof of "Amortized cost of $\text{Find-Set}$ operation is $O(\alpha(n))$" from CLRS
I was reading the section of Data Structures for Disjoint Sets from the text Introduction to Algorithms by Cormen et. al. I made it through the proof, but I'm not sure I understand the very last ...
- 67
2
votes
0
answers
785
views
Accounting method vs Potential method for analysing an augmented stack and differences with standard complexity analysis
With reference to chapter 17 of CLRS, (Amortized analysis). I'm trying to understand the differences between the accounting method and the potential method.
Let's start with standard analysis of the ...
- 703
2
votes
0
answers
378
views
Amortized time complexity of append on a dynamic array that resizes according to geometric base 1.25?
I'm trying to prove that the amortized time complexity of appending to a dynamic array that resizes in accordance with capacity = $N$ to $N+\lceil{\frac{N}{4}}\rceil$ is $O(1)$. I'm assuming that ...
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
2
votes
0
answers
187
views
How to compute amortized complexity of n runs of Dijkstra's algorithm?
I'm trying to figure out how to compute an amortized complexity/ or complexity of this algorithm. We have a Graph which is oriented. And we are going to run Dijkstra's algorithm for finding a shortest ...
- 339
2
votes
0
answers
110
views
What is hiding behind amortized constant delay enumeration?
The following may contain errors. It is precisely because I am not
sure I understand the topic that I am asking questions. I do not have
books about it and could not find an adequate reference on the ...
- 19.4k
1
vote
0
answers
17
views
Algorithm for an incremental update to cut vertex set
There is a classic linear algorithm to find every cut vertex (AKA articulation point) in a graph.
I have a usecase that does this computation after every time a non-articulation-point is inserted or ...
- 11
1
vote
0
answers
72
views
Priority Queues with $DecreaseKey,FindMin,Insert$ in time $O(1)$, $DeleteMin$ in $ O(\log n)$ and $IncreaseKey$ in $O(1)$, Amortized
Problem:
In this problem, we discuss Data-Structures that maintain a group of ordered elements.
We must support the operations $ DecreaseKey, FindMin, Insert $ in time $ O(1) $ and the operation $ ...
- 233
1
vote
2
answers
325
views
Amortized Analysis of extract-min-operation of Fibonacci Heap
I am studying the operations of the Fibonacci heap. While going through min-extraction operation every step and its complexities are fairly clear to me. In short, it is:
The potential before ...
- 11
1
vote
0
answers
92
views
Fibonacci Heap that consolidates after every step
The lecturer of my graduate algorithms course suggested that, even if a Fibonacci Heap would consolidate its tree list after every operation (not just when doing deleteMin()), most operations would ...
- 11
1
vote
0
answers
205
views
Dynamic array with 4x growth factor: Potential Method
I am curious on the use of the potential method for amortized analysis for a dynamic array which quadruples in size after it becomes full.
I understand how the potential function is defined and used ...
- 11
1
vote
0
answers
59
views
Splay tree amortized analysis cost using Access Lemma
Currently studying for an algorithms exam and I came across this question and solution, but I can't understand the solution where it references nodes of depth less than $4\log n$ and not restructuring....
- 11
1
vote
0
answers
99
views
Is there a known way to make an efficient, compact, and fully persistent stack or queue?
In the world of mutable/ephemeral data structures and imperative programming languages, one of the classic ways to implement a stack or queue is to use array doubling: use mutation to fill up or empty ...
- 409
1
vote
0
answers
182
views
Is using Fibonacci Heaps in Huffman Code, better than a regular Min-heap?
When using Huffman Code, to generate prefix-code trees for a sequence of letters, CLRS choose to use a normal Min-heap data structure.
Using Fibonacci-heaps instead, are we not able to achieve a ...
- 133
1
vote
0
answers
23
views
When was the dynamic array first introduced as an example for amortized analysis?
I'm writing a report on amortized analysis, and I'm using the example of a dynamic array to explain each method. I think it would be nice to add a reference to when this example was first used, as it ...
- 11
1
vote
0
answers
224
views
Sequence of operations of Union-Find of length $m$ ($n$ being the number of Make-Set operations) with time complexity in $\Omega(m\log n)$
In Union-Find with link-by-rank but no path compression find a sequence of operations Make-Set, Find, Union of length $m$, containing $n$ Make-Set operations, and with time complexity in $\Omega(m\log ...
- 169
1
vote
0
answers
58
views
amortized analysis
I am trying to find a general solution for the given A,B,C in dynamic arrays. Those veriables presents factors in the following operations :
given :
c_i the size of the array after operation O_i (...
- 21
1
vote
0
answers
93
views
Why is maximum size of root is 2n + 1 in Splay trees?
In the amortized analysis of Splaying in Dynamic trees, let us consider a splay tree $T$ with $n$ keys and $v$ be a node of $T$. We define $size(v)$ as the number of nodes in the subtree rooted at $...
- 163
1
vote
0
answers
98
views
Calculating the cost for each operation in amortized analysis
According to what I've read in the CLRS book , we calculate the amortized cost for a complete set , and not for a single operation.But in an exam question , it was asked about an operation amortized ...
- 53
1
vote
0
answers
49
views
Is it true that the potential method is usually the inverse of the accounting method in the context of amortized analysis?
I remember reading this somewhere (will post the source as soon as I find it), but was wondering, if anyone knows why this is true or has maybe an example to portray why this is the case.
- 3,000
1
vote
0
answers
563
views
Potential method analysis for Insert and Extract-max on a Max heap data structure
Suppose that you do some sequence of operations on a max heap, in this case only Insert and Extract-max. Whenever the heap ...
- 619
0
votes
0
answers
25
views
Amortized analysis on skew heap arbitrary deletion
A practice problem in my textbook asks to proof the amortized complexity for a sequence of insert, delete min, and decrease-key operations on an initially empty skew heap. Insert and delete min both ...
- 25
0
votes
0
answers
53
views
Potential method: prove that dynamic table compaction runs in amortized constant time
Suppose we are given a dynamic table $T$. After the $i$th operation, $num_i$ is the number of elements stored in $T$, and $size_i$ is the capacity of $T$. Let
$$
\alpha_i = \frac{num_i}{size_i}
$$
be ...
- 52
0
votes
1
answer
55
views
Prove with potential method that dynamic table with $q > 1$ expansion runs in amortized constant time
Suppose I have a dynamic table supporting $Insert$ procedure, which sets an input value after the tail of the dynamic table. If the underlying table is already full, we multiply its size by $q > 1$....
- 52
0
votes
0
answers
42
views
Understanding David Pisinger's balanced algorithm for the subset-sum problem with bounded weights
I'm trying to understand David Pisinger's balanced algorithm for the subset-sum problem with bounded weights, which can be found on page 5 of his paper Linear Time Algorithms for Knapsack Problems ...
- 159
0
votes
3
answers
92
views
Algorithm with amortized time complexity
While I understand the process of considering/observing an algorithm and finding an average time, necessary to perform an operation that happens in this algorithm, I still cannot quite gasp the idea, ...
- 185
0
votes
0
answers
400
views
Analyzing Hybrid Merge and Insertion Sort
We know that merge sort takes O(n log n) and insertion sort takes (n^2) for worst case.
The combination of these two algorithm is to speed up and reduce key comparisons, as for a subarray with small ...
0
votes
0
answers
43
views
Amortized cost depending on the number of operations
Considering a dynamic array that grows by a constant factor $k$ (the new array has $k$ more cells than the last one) each time the array is full which initially has $n$ elements in it. Calculating the ...
- 243
0
votes
0
answers
96
views
General Proof on Potential Method and Amortized Analysis
Let $T$ be an arbitrary data structure for a dynamic set. For every state T of $T$, let $d_t \in \mathbb{N}$. Observe two Operations $O_1, O_2$ on $T$ whose runtimes are proportional to $d_t$ and $...
- 13
0
votes
0
answers
100
views
Can you delete-min from fibonacci heap in O(1) amortized?
I just had a data-structures exam. One of the questions asked us to create a data structure which allowed insert operations in O(logn) amortized and delete-max (or min, doesn't matter) in O(1) ...
0
votes
0
answers
123
views
Create a potential function for an abstract queue data structure to show constant amortized-time complexity
Consider a variation of a Queue called MaxQueue, Q, that has the following operations:
dequeue(Q): removes and returns the first element of Q
enqueue(Q, s): Appends the integer s to the end of Q
...
- 11
0
votes
0
answers
246
views
Intuition behind the entire (amortized) concept of Fibonacci Heap operations
The following excerpts are from the section Fibonacci Heap from the text Introduction to Algorithms by Cormen et. al
The potential function for the Fibonacci Heaps $H$ is defined as follows:
$$\Phi(H)...
- 1,112
0
votes
0
answers
24
views
Does amortized algorithm analysis make any assumptions about the sequence of function calls?
I have read that average case analysis makes some assumptions about the inputs to the data structure, and amortized analysis makes no such assumptions.
Does amortized analysis make any assumptions ...
- 133
0
votes
0
answers
254
views
if binary heap potential function is c*size(binary heap)) then insert will not take O(logn)and extract min will not take O(1) amortized time
So i want to prove that if i choose a potential function for binary heap as any constant*size of the binary heap (n is the number of nodes) then my insert will not have O(logn) amortized cost and ...
- 1
0
votes
0
answers
267
views
Analysis of Union-Find(Disjoint Sets)
I have been trying to learn more about amortized analysis. Recently I came across the Disjoint Sets or Union-Find structures. I am using union by rank and path comparison. The potential of such data ...
0
votes
0
answers
485
views
Amortized cost of decimal counter
Can somebody tell me what the lowest amortized cost for the increment operation of a decimal counter is?
I can show the costs are O(1) and with max amortized costs of 2 (similar to a binary counter), ...
0
votes
0
answers
255
views
Amortised complexity of dynamic array using potential function
I'm trying to find out how potential function works. I'm trying to compute an amortised complexity of $n$ operations on dynamic array. To make it simple, assume, that we can't delete items and we can ...
- 339
-1
votes
1
answer
587
views
What is the amortized time complexity of inserting an element to this heap?
Assume you implement a heap using an array and each time the array is full, you copy it to an array double its size. What is the amortized time complexity (for the worst case) of inserting elements ...
- 111
-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 ...
