Questions tagged [amortized-analysis]
A method in analysis of algorithms that considers the overall cost of a sequence of operations.
22
questions with no upvoted or accepted answers
6
votes
0answers
1k 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?
3
votes
0answers
963 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 ( ...
2
votes
0answers
68 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 ...
2
votes
0answers
218 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
0answers
96 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 ...
2
votes
0answers
127 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 ...
2
votes
0answers
97 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 ...
1
vote
0answers
11 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 ...
1
vote
0answers
124 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 ...
1
vote
0answers
325 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 ...
1
vote
0answers
55 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 (...
1
vote
0answers
31 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 $...
1
vote
0answers
88 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 ...
1
vote
0answers
43 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.
1
vote
0answers
358 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 ...
0
votes
0answers
27 views
Splay tree amortized cost analysis
I am looking into the amortized analysis of splay trees and seem to be missing something.
Pretty much every resource uses the accounting method which I believe I grasp.
What confuses me is the part ...
0
votes
0answers
73 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 ...
0
votes
0answers
216 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
0answers
210 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
0answers
189 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 ...
-1
votes
1answer
342 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 ...
-1
votes
1answer
277 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 ...
