New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

# Questions tagged [amortized-analysis]

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

43 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?
257 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 ...
• 223
118 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 ...
• 713
1k views

• 233
1 vote
387 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
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 ...
1 vote
236 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
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....
• 11
1 vote
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 ...
• 409
1 vote
187 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 ...
• 143
1 vote
23 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
226 views

• 173
1 vote
98 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
49 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.
• 3,040
1 vote
584 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 ...
• 629
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 ...
• 25
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$....
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 ...
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 ...