# Questions tagged [amortized-analysis]

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

38 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
2k views

### Choosing potential function in amortized analysis

How should I think to choose the potential function in the amortized analysis? More specifically are there techniques or tips for choosing optimal or good potential functions?
97 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 ...
• 209
107 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 ...
• 663
1k views

• 233
1 vote
73 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
1 vote
56 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 ...
1 vote
122 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
1 vote
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
1 vote
85 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 ...
• 409
1 vote
125 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
1 vote
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
1 vote
169 views

• 163
1 vote
96 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 ...
• 53
1 vote
48 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,920
1 vote
499 views

### Potential method analysis for Insert and Extract-max on a Max heap data structure

Suppose that you do some sequence of operations on a max heap, in this case only Insert and Extract-max. Whenever the heap ...
• 599
16 views

### Give examples of data structure usage which can be used and cannot be used in amortized analysis

Preparing for my finals in my "advance algorithms" course. In one of the previous exams, there was the following question: Let there be some arbitrary data structure (it is not known ...
• 209
43 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, ...
• 173
122 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 ...
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 ...