Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [amortized-analysis]

A method in analysis of algorithms that considers the overall cost of a sequence of operations.

Filter by
Sorted by
Tagged with
-2 votes
1 answer
87 views

Amortized cost for Stack Operations

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 $B$):   PushA($x$): Push element $x$ on stack $A$.   ...
Avin's user avatar
  • 1
1 vote
0 answers
61 views

Amortized analysis of dynamic array insertion

I learned the amortized analysis of Prof Demaine's 6.006 videos. The Erik's thesis was, If we reallocate memory by doubling capacity => $$1 +2+4 + 8 + 16 +..+n = \theta(2^{lgn}) = \theta(n)$$ From ...
Huseyin Okan Demir's user avatar
1 vote
1 answer
83 views

Amortised cost - transferring tokens

I'm trying to solve a problem from one of the older exams. Question: There's an infinite, one-dimensional board, with fields numbered consecutively $\ldots, -2, -1, 0, 1, 2, \ldots$ A move in the ...
Michał's user avatar
  • 113
0 votes
0 answers
38 views

Amortized analysis on skew heap arbitrary deletion

A practice problem in my textbook asks to proof the amortized complexity for a sequence of insert, delete min, and decrease-key operations on an initially empty skew heap. Insert and delete min both ...
Tomyy's user avatar
  • 25
0 votes
1 answer
89 views

Prove with potential method that dynamic table with $q > 1$ expansion runs in amortized constant time

Suppose I have a dynamic table supporting $Insert$ procedure, which sets an input value after the tail of the dynamic table. If the underlying table is already full, we multiply its size by $q > 1$....
coderodde's user avatar
1 vote
0 answers
63 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 ...
Pablo Messina's user avatar
0 votes
1 answer
43 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 ...
Proper Illumination's user avatar
2 votes
0 answers
123 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 ...
Hugh Mann's user avatar
2 votes
1 answer
582 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 $...
alienhunter's user avatar
1 vote
1 answer
184 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 ...
ryan chandra's user avatar
0 votes
1 answer
40 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 ...
P_Gate's user avatar
  • 103
1 vote
0 answers
20 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 ...
homa_rano's user avatar
2 votes
2 answers
296 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 ...
JsonResponse's user avatar
0 votes
1 answer
516 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 ...
ISeekTheWisdom's user avatar
5 votes
0 answers
258 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 ...
vesii's user avatar
  • 223
0 votes
3 answers
154 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, ...
imbAF's user avatar
  • 185
1 vote
0 answers
82 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 $ ...
flamel12's user avatar
  • 233
2 votes
1 answer
929 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 ...
Aditya's user avatar
  • 115
3 votes
2 answers
812 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, ...
flamel12's user avatar
  • 233
2 votes
1 answer
353 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}$. ...
SVMteamsTool's user avatar
1 vote
1 answer
153 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 ...
grozby's user avatar
  • 21
2 votes
1 answer
215 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 ...
African_king's user avatar
1 vote
2 answers
388 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 ...
suman's user avatar
  • 11
0 votes
0 answers
451 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 ...
xineta5158's user avatar
0 votes
0 answers
45 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 ...
user183748292's user avatar
4 votes
1 answer
272 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 ...
Or Bairey-Sehayek's user avatar
0 votes
0 answers
97 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 $...
jugc's user avatar
  • 13
0 votes
1 answer
380 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 ...
yuval's user avatar
  • 49
1 vote
1 answer
542 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 ...
yuval's user avatar
  • 49
0 votes
1 answer
195 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 ...
Or Bairey-Sehayek's user avatar
7 votes
1 answer
503 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 ...
hLk's user avatar
  • 235
0 votes
0 answers
110 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) ...
Amitai Gottlieb's user avatar
1 vote
0 answers
100 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 ...
reservoir's user avatar
1 vote
0 answers
240 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 ...
default's user avatar
  • 11
0 votes
1 answer
155 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)$ ...
Lisa Berry's user avatar
3 votes
1 answer
164 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 ...
Leo's user avatar
  • 33
0 votes
0 answers
127 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 ...
felicef885's user avatar
6 votes
1 answer
103 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 ...
Justin Solomon's user avatar
1 vote
1 answer
216 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 ...
Abhishek Ghosh's user avatar
0 votes
0 answers
266 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)...
Abhishek Ghosh's user avatar
1 vote
0 answers
64 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....
D Wot's user avatar
  • 11
2 votes
1 answer
119 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]$...
Abhishek Ghosh's user avatar
1 vote
0 answers
101 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 ...
dfeuer's user avatar
  • 409
1 vote
2 answers
295 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 ...
Hugh's user avatar
  • 119
1 vote
1 answer
234 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 ...
Silver Flash's user avatar
0 votes
0 answers
25 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 ...
Joff's user avatar
  • 155
1 vote
0 answers
188 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 ...
NewDev90's user avatar
  • 143
0 votes
1 answer
467 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)....
Nix's user avatar
  • 83
1 vote
1 answer
844 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 ...
gimmeshelter's user avatar
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: <...
Geralt's user avatar
  • 113