# Questions tagged [amortized-analysis]

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

35 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1k 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?
98 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 ...
1k views

637 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 ...
56 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 (...
66 views

32 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) ...
49 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 ...
73 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 ...
120 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)...
20 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 ...
153 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 ...
246 views

### Analysis of Union-Find(Disjoint Sets)

I have been trying to learn more about amortized analysis. Recently I came across the Disjoint Sets or Union-Find structures. I am using union by rank and path comparison. The potential of such data ...
292 views

### Amortized cost of decimal counter

Can somebody tell me what the lowest amortized cost for the increment operation of a decimal counter is? I can show the costs are O(1) and with max amortized costs of 2 (similar to a binary counter), ...
222 views

### Amortised complexity of dynamic array using potential function

I'm trying to find out how potential function works. I'm trying to compute an amortised complexity of $n$ operations on dynamic array. To make it simple, assume, that we can't delete items and we can ...
### Custom binary counter supports only increment in $2^i$ values amortized analysis
I'm a having trouble analyzing this algorithm. This is a binary counter that supports only increments in $2^i$ values it's implemented in this way: starting from the $i$-th location change all the ...