Questions tagged [amortized-analysis]
A method in analysis of algorithms that considers the overall cost of a sequence of operations.
144
questions
0
votes
0
answers
33
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
85
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, ...
CommunityBot
- 1
1
vote
2
answers
214
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 ...
CommunityBot
- 1
0
votes
1
answer
24
views
Splay Trees - Sequential Access Theorem & lower bound for comparison-based sorting
The following theorem was proven by R.E. Tarjan in 1984:
Theorem (Sequential Access Theorem). If we access each of the nodes of an arbitrary initial tree once, in symmetric order, the total time ...
- 27.4k
2
votes
0
answers
114
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 ...
- 33
7
votes
1
answer
457
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
2
votes
1
answer
181
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 $...
- 2,590
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]$...
- 12.3k
1
vote
1
answer
110
views
Aggregate method for dynamic table (amortized analysis)
For amortized analysis (aggregate method), dynamic table insertion cost can be divided into:
if no expansion, then cost = 1
if we expand the table, then cost = i (if i-1 is an exact power of 2)
then ...
- 1,018
0
votes
0
answers
41
views
What binary search tree to use if probabilities of element query are known apriori?
There is a universal set of integer pairs $(key; outcomes)$, a subset of which is inserted into a binary search tree in $O(\log n)$ time for each key and can be searched by keys. Afterwards a large ...
- 287
0
votes
1
answer
36
views
What are the actual costs $c_i$ in the potential method?
In "Introduction to Algorithms" by Cormen et al. the Potential Method is explained. For example, we have the following representation for the amortized costs of the i-th operation with ...
- 2,590
1
vote
0
answers
16
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
2
votes
2
answers
241
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 ...
- 38.5k
0
votes
0
answers
35
views
Choosing potential function in amortized analysis when knowing the initial and final state of our data structure
I've some trouble understanding how to choose the potential function in aggregate analysis, more specifically in the solution to this exercise from the book "Introduction to algorithms - Thomas H....
0
votes
1
answer
410
views
Potential Method For Decimal Counter
There is a counter that counts the number of items in the store. For every increase in item or item that has been inserted, the cost is a + kb where k is the number of digits that has been changed in ...
- 27.4k
5
votes
0
answers
198
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
1
vote
0
answers
68
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
3
votes
2
answers
484
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, ...
- 3,290
2
votes
1
answer
811
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 ...
- 27.8k
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: ...
- 746
2
votes
1
answer
200
views
Cost of increasing a binary counter with a starting value n times
Consider a k-bit binary counter and suppose that in the beginning the value of the i-th most significant bit is $b_i$ for each $i = 0, . . . , k − 1$. Let $b = b_0 + 2b_1 +· · · + 2^{k−1}
b_{k−1}$. ...
- 38.5k
1
vote
1
answer
129
views
Amortized analysis (accounting/banker's method) for tree operations
Suppose we have a tree data structure with root $r$ with two operations:
Add($x, y$) - adds the node $y$ as a child to the node $x$
Zip($x$)- this makes the node $x$ and all of $x$'s ancenstors direct ...
- 2,590
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 ...
- 71.9k
2
votes
1
answer
203
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 ...
- 38.5k
0
votes
0
answers
374
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
41
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 ...
- 5,266
4
votes
1
answer
247
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 ...
- 274k
0
votes
1
answer
257
views
Changing binary counter structure such that increament and decreament methods will work in O(1) amortized
Just trying to solve the second part of a question with two parts.
First part was to prove that you can't add decrement method to a standart binary counter without hurting the amortized complexity and ...
CommunityBot
- 1
0
votes
0
answers
93
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
1
vote
1
answer
396
views
Accounting method - dynamic array
I want to compute the amortize time of a type of dynamic array (inserting such that if i have no place to insert i am multipling the array by (1+a) (a is between 0 to 1).
I need to compute the time ...
- 13.3k
6
votes
2
answers
811
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 ...
- 101
0
votes
1
answer
144
views
Amortized analysis - adding operations to a data structure
One of the finer points of amortized analysis about which I have been able to find relatively little information is the broad question of what happens to the amortized cost of a structure's existing ...
D.W.♦
- 154k
0
votes
1
answer
136
views
In Amortized Analysis, can we chose how big $n$ is?
Suppose I want to show by contradiction that the amortized cost of a data structure with some operations cannot be less then $\Theta(k)$. I assume for the sake of contradiction that it is possible. ...
1
vote
1
answer
179
views
Amortized analysis for disjoint sets' find-set(x) function (from CLRS)
I start off by apologizing for the fact that I don't really know how to use latex/markdown. My question, however, is directly from the Introduction To Algorithms book by Cormen et al. The topic ...
- 274k
0
votes
0
answers
80
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) ...
1
vote
0
answers
82
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
196
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
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 ...
- 711
0
votes
1
answer
149
views
design a strange data structure, is it possible?
I need a FIFO QUEUE that can do Insert and Remove from Queue in amortized $O(1)$ but extract min in $O(log n)$. is it possible?
When just find min is important (not removing) there is lots of $O(1)$ ...
- 92
3
votes
1
answer
121
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 ...
- 3,562
2
votes
2
answers
627
views
how to verify permutation generated in constant amortized time?
Here is an algorithm that generates the next permutation in lexicographic
order, changing the given permutation in-place:
Find the largest index k such that a[k] < a[k+1]. If no such index exists, ...
- 11
6
votes
1
answer
100
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 ...
- 729
0
votes
0
answers
119
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
...
- 965
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?
- 103
1
vote
1
answer
190
views
Difficulty in few steps in proof of "Amortized cost of $\text{Find-Set}$ operation is $\Theta(\alpha(n))$"assuming union by rank, path compression
I was reading the section of data structures for disjoint sets from the text Introduction to Algorithms by Cormen et. al .I faced difficulty in understanding few steps in the proof of the lemma as ...
- 13.9k
0
votes
0
answers
220
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,092
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 ...
- 1,092
1
vote
0
answers
53
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....
- 7,768
1
vote
0
answers
97
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
2
answers
239
views
Amortized time for dynamic array
I'm struggling to understand one part from the book "Cracking the coding interview".
The author states inserting an element in a dynamic array is $O(1)$ most of the time, except when the array is full ...
- 119