Questions tagged [amortized-analysis]
A method in analysis of algorithms that considers the overall cost of a sequence of operations.
0
votes
0answers
21 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
1answer
33 views
Best known (state of science) time complexity of an array access problem
Consider an Array $A$ with $n$ values and the following operations:
get(i): Returns the value of $A[i]$
insert (x): Insert the element x into the any free place in A (not necessarily in $A[x]$ or the ...
2
votes
0answers
38 views
Algorithm to optimize redistribution of balls amongst urns [closed]
Here is the question:
Say we have k urns with 1 ball in each urn. At each iteration of the game, I pick one urn and redistribute its contents amongst other urns and each urn can receive at most one ...
2
votes
2answers
117 views
Constant factor of an array
In Elements of Programming Interviews in Python by Aziz, Lee and Prakash, they state on page 41:
Insertion into a full array can be handled by resizing, i.e.,
allocating a new array with ...
3
votes
1answer
490 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
64 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
72 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
59 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
90 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
219 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
96 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
37 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
53 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
258 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
114 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
208 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
49 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
261 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
291 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
69 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
509 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
330 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
271 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
52 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
184 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 ...
1
vote
2answers
202 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
124 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
445 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
482 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
974 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
643 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
233 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
204 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
93 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
3k 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
32 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
2k 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
186 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 ...
3
votes
1answer
107 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 ...
-1
votes
1answer
308 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
170 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 ...
3
votes
0answers
116 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
86 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
900 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
566 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.
...
