Questions tagged [amortized-analysis]
A method in analysis of algorithms that considers the overall cost of a sequence of operations.
116
questions
0
votes
0answers
10 views
Amortized Analysis on Binary Heap, Potential Method
The potential function of a Binary Heap is given as the sum of levels of every node in the Binary Heap. For example,potential of a Binary Heap with 6 nodes is 0 + 2 ∗ 1 + 3 ∗ 2 = 8.
It is given that ...
0
votes
0answers
22 views
sum selected nodes of a set in $\log n$ time
Given a sum operation of a dynamic set $S$ of length $n$ which includes integer pairs $(x, y)$. The sum operation is defined as taking two inputs $a$ and $b$ such that $a \leq b$. The sum operation ...
0
votes
0answers
44 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
...
6
votes
1answer
63 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 ...
2
votes
1answer
60 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 ...
1
vote
0answers
27 views
Essence of the cost benifit obtained by using “markings” in Fibonacci Heaps (by using a mathematical approach)
The following excerpts are from the section Fibonacci Heap from the text Introduction to Algorithms by Cormen et. al
The authors deal with a notion of marking the nodes of Fibonacci Heaps with the ...
1
vote
0answers
36 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
vote
0answers
13 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....
3
votes
1answer
65 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]$...
1
vote
0answers
55 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 ...
1
vote
2answers
52 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 ...
0
votes
0answers
41 views
Choosing potential function in amortized analysis of the dynamic array
Suppose we have a dynamic array with some initial capacity $c_{initial}$ (i.e., the dynamic array with zero elements will have this capacity). The $add$ operation is modified the following way:
New ...
1
vote
0answers
58 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 ...
0
votes
0answers
18 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 ...
1
vote
0answers
48 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 ...
0
votes
1answer
74 views
Amortized value of dequeue with potential function
A deque is implemented with 3 stacks. one for the head, one for the tail and one is always empty.
Pushing is therefor O(1), light popping (in case the head/tail respectively aren't empty) is also O(1)....
1
vote
1answer
62 views
Can someone let me know if my understanding of amortized run time in a dynamic array list is correct?
Am I right in my understanding for amortized time for insertion in a dynamic array list? (dynamic means create a copy double its size and copy existing elements to new one WHEN we reach the current ...
1
vote
1answer
59 views
converting for loop into mathematical notation
I am a bit confused with a problem that I am having.I am trying to do an amoritized analysis and I am able to represent the function that I want to use using code. I coded the function as follows:
<...
0
votes
0answers
25 views
The accounting Method analysis for table expansion by tripleling instead of doubling an array
If we double the array every time we get the amortized cost of 3n or 3$ if you prefer.
I was wondering what would it be if we tripled the array size instead of doubling it.
The rational between the ...
1
vote
0answers
17 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 ...
0
votes
1answer
58 views
What time complexity is more significant? [closed]
A certain algorithm executes $n$ operations of three types: insert, delete, and find.
We know that $n/10$ of the operations are inserts, and the rest are deletes and finds.
You are given two ...
1
vote
1answer
662 views
Amortized analysis - increment in ternary counter [closed]
What is the amortized analysis of increment action in a ternary counter that is initialized to 0?
2
votes
3answers
793 views
Can an algorithm with $\Theta(n^2)$ run time be faster than an algorithm with $\Theta(n\log n)$ run time?
This is a question posted for extra practice (i.e., not for credit):
Can an algorithm with $\Theta(n^2)$ run time be faster than an algorithm with $\Theta(n\log n)$ run time? Explain.
I'm not sure ...
0
votes
1answer
45 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
49 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
200 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
500 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
239 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
181 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
112 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
237 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
338 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
228 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
160 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
81 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 ...
9
votes
1answer
690 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
138 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
471 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 ...
3
votes
0answers
88 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
1answer
422 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 ...
2
votes
1answer
499 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
90 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
2answers
1k 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
607 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
72 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
395 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
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 (...
2
votes
0answers
289 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
417 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 (...
