Questions tagged [amortized-analysis]
A method in analysis of algorithms that considers the overall cost of a sequence of operations.
3
votes
1answer
480 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 ...
1
vote
1answer
47 views
general question amortized cost and worst case
lets say a data structure has operations called insert and delete both of which take O(log(n)) worst case. Suppose the amortized cost of insert is O(log(n)) and the amortized cost of delete is O(1).
...
0
votes
1answer
51 views
How to do if a potential function Does not work? Amortized analysis
Here is an example taken from CLRS.
q)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 ...
0
votes
0answers
50 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
vote
2answers
78 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 ...
2
votes
2answers
169 views
Amortized analysis of max-heap
Consider an ordinary binary max-heap data structure with $n$ elements that supports insert and extract-max in $O(\log n)$ worst-case time.
Question: If extract max is $O(1)$ amortized does that ...
1
vote
1answer
60 views
amortized analysis of max heap
Q) Consider an ordinary binary max-heap data structure with n elements that supports insert and extract-max in $O(log(n))$ worst-case time. Give a potential function $\Phi$ such that the amortized ...
1
vote
1answer
23 views
Amortized time complexity for double stack emulated queue
Assume that we have a data type $stack$ which has two operation $push$ and $pop$, both operations' time complexity is $O(1)$ in worst case. The $stack$ also has a property $size$ indicate how many ...
0
votes
1answer
51 views
The validity of the potential function for splay tree
The paper "Self-Adjusting Binary Search Trees" defines (Page 658) the potential function for analyzing the amortized cost of a sequence of $m$ splay operations as the sum of the ranks of all nodes in ...
7
votes
1answer
204 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 ...
1
vote
0answers
98 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 ...
0
votes
0answers
178 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
47 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 ...
1
vote
1answer
237 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 ...
1
vote
1answer
270 views
Data structure with Median, Min, Max, Delete in $O(1)$ amortized-time
I'm looking for a data structure, in which the operations $Init, Median, Min, Max, Delete$ run in $O(1)$ amortized-time, and $Insert$ should run in amortized-time as low as possible.
I tried to work ...
3
votes
1answer
2k 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 ...
0
votes
1answer
67 views
Does the following algorithm has amortized constant time per element?
Consider the following streaming ``algorithms'':
When an element $x$ arrives, flip a fair coin until it shows ``heads''.
Fix a random hash function $h:U\to\{0,1\}^\infty$ (i.e., it maps elements into ...
3
votes
1answer
483 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$ ...
0
votes
1answer
307 views
Amortized analysis of resizing array implementation of a stack
Here is an excerpt from the book Algorithms, 4th edition by R. Sedgewick and K. Wayne:
Proposition E. In the resizing array implementation of Stack
(Algorithm 1.1), the average number of array ...
0
votes
1answer
53 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. ...
0
votes
1answer
254 views
Amortized time of insertion into an Array list
According to 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'...
1
vote
0answers
50 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 (...
2
votes
0answers
178 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
2answers
186 views
Potential function for stack problem
Consider the follow operations on a stack of size at most $k$.
Push - insert element in the stack - actual cost 1
Pop - remove top element from the stack - actual cost 1
Copy - copy whole stack (...
0
votes
1answer
121 views
How to compare an experimental study with amortized times
I have an implementation of a data structure I have to study for a group project (Fibonacci heaps if you're interested).
I'm asked to compare the theoretical results of the operations in amortized ...
4
votes
1answer
408 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 (...
5
votes
1answer
466 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. ...
1
vote
1answer
895 views
Accounting method amortized analysis of a sequence of operations (CLRS 17.2-2)
I'm working through CLRS, Chapter 17 on Amortized Analysis. One of the problems I attempted to solve is 17.2-2 (described below), but my answer differs from the one in the instructor's manual, so I ...
0
votes
1answer
625 views
Amortized analysis for dynamic array - how to come up with a potential function?
I learned about amortized analysis and the potential method, I also
leaned an example of a binary counter which I think I understand well.
In the case of the binary counter I understand the choice of ...
1
vote
1answer
220 views
Height and depth of every node in Path Compression
If we have an union-find(disjoint-set) data structure and we are doing an union by rank and path compression for a find operation, how would the depth and height of every node change after the find ...
0
votes
0answers
183 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 ...
2
votes
0answers
92 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 ...
1
vote
0answers
30 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 $...
4
votes
1answer
2k 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 ...
1
vote
1answer
30 views
Is the potential difference in the two consecutive states of a data structure equal to the credit of the change inducing operation?
I am following CLRS for studying Amortized analysis with potential function and there I came through the following :
Let a data structure go through states : $D_0 $ $D_1$ $D_2$ $ ....$ $D_n$ while ...
2
votes
1answer
1k views
How does the token method of amortized analysis work in this example?
Below is the description of the answer to a question which says the following:
Design a data structure to support two operations for a dynamic multiset S of integers which allows duplicate values.
...
0
votes
0answers
170 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), ...
3
votes
1answer
2k 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 ...
4
votes
1answer
102 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 ...
-2
votes
1answer
301 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 ...
0
votes
0answers
165 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 ...
4
votes
0answers
107 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 ...
1
vote
0answers
83 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 ...
3
votes
0answers
866 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 ( ...
3
votes
1answer
556 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 ...
1
vote
1answer
45 views
What does it mean when each individual array is sorted in different array but bear no relationship to each other
There's a textbook problem that talks about making a binary search dynamic, then analyzing for its amortize cost. However I'm not exactly sure what is the organization scheme of this data structure.
...
1
vote
1answer
516 views
Reb-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 proved?
5
votes
1answer
2k 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:
$$ \...
1
vote
0answers
38 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.
2
votes
1answer
68 views
Why does the total credit associated with a data structure must be nonnegative at all times for the accounting method?
I was reading CLRS and it said in the chapter for the accounting method (for amortized analysis):
the total credit associated with the data the structure must
be nonnegative at all times.
where ...
