Questions tagged [amortized-analysis]
A method in analysis of algorithms that considers the overall cost of a sequence of operations.
131
questions
1
vote
0
answers
41
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 $ ...
- 223
1
vote
1
answer
552
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 ...
- 111
3
votes
2
answers
201
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, ...
- 223
2
votes
1
answer
58
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}$. ...
- 369
1
vote
1
answer
76
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 ...
- 21
2
votes
1
answer
162
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 ...
- 45
1
vote
1
answer
58
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 ...
- 11
0
votes
0
answers
106
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
36
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 ...
- 243
4
votes
1
answer
204
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 ...
0
votes
0
answers
65
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
0
votes
1
answer
99
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 ...
- 49
1
vote
1
answer
186
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 ...
- 49
0
votes
1
answer
71
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 ...
5
votes
1
answer
303
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 ...
- 195
0
votes
0
answers
45
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
55
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
108
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
0
votes
1
answer
124
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)$ ...
3
votes
1
answer
67
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 ...
- 33
0
votes
0
answers
101
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
...
- 11
6
votes
1
answer
94
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 ...
- 161
1
vote
1
answer
126
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,034
0
votes
0
answers
164
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,034
1
vote
0
answers
41
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....
- 11
2
votes
1
answer
94
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,034
1
vote
0
answers
84
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 ...
- 399
1
vote
2
answers
127
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
1
vote
1
answer
125
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 ...
- 205
0
votes
0
answers
21
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 ...
- 133
1
vote
0
answers
119
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 ...
- 123
0
votes
1
answer
171
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)....
- 83
1
vote
1
answer
522
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 ...
- 13
1
vote
1
answer
71
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:
<...
- 113
1
vote
0
answers
22
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 ...
- 11
0
votes
1
answer
60
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 ...
- 3
1
vote
1
answer
1k
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?
- 29
2
votes
3
answers
3k
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 ...
- 23
0
votes
1
answer
69
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 ...
- 130
2
votes
0
answers
54
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 ...
- 121
2
votes
2
answers
297
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 ...
- 123
3
votes
1
answer
516
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 ...
- 203
1
vote
1
answer
458
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).
...
- 129
0
votes
1
answer
329
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 ...
- 129
0
votes
0
answers
203
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
2
votes
2
answers
900
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 ...
- 55
2
votes
2
answers
583
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 ...
- 35
1
vote
1
answer
541
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 ...
- 35
1
vote
1
answer
504
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 ...
- 123
0
votes
1
answer
182
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,209