# Questions tagged [amortized-analysis]

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

116 questions
Filter by
Sorted by
Tagged with
10 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 ...
22 views

### sum selected nodes of a set in $\log n$ time

Given a sum operation of a dynamic set $S$ of length $n$ which includes integer pairs $(x, y)$. The sum operation is defined as taking two inputs $a$ and $b$ such that $a \leq b$. The sum operation ...
44 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 ...
63 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 ...
60 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 ...
27 views

### Essence of the cost benifit obtained by using “markings” in Fibonacci Heaps (by using a mathematical approach)

The following excerpts are from the section Fibonacci Heap from the text Introduction to Algorithms by Cormen et. al The authors deal with a notion of marking the nodes of Fibonacci Heaps with the ...
36 views

499 views

### Data structure with Median, Min, Max, Delete in $O(1)$ amortized-time

I'm looking for a data structure, in which the operations $Init, Median, Min, Max, Delete$ run in $O(1)$ amortized-time, and $Insert$ should run in amortized-time as low as possible. I tried to work ...
2k views

### Why is a sequence of n Push, Pop, Multipop operations O(n²)?

From "Introduction to Algorithms" by Cormen, Leiserson, Rivest, Stein, Third Edition, page 453: Let us analyze a sequence of $n$ Push, Pop, Multipop operations on an initially empty stack. The ...
90 views

### Does the following algorithm has amortized constant time per element?

Consider the following streaming algorithms'': When an element $x$ arrives, flip a fair coin until it shows heads''. Fix a random hash function $h:U\to\{0,1\}^\infty$ (i.e., it maps elements into ...
1k views

### Finding potential function for dynamic array

About dynamic array, doubling it's size with every element that is beying its limit: From what I understand, the number of operations between the $n$th element and the $n+1$th depending on if $n+1$ ...
607 views

### Amortized analysis of resizing array implementation of a stack

Here is an excerpt from the book Algorithms, 4th edition by R. Sedgewick and K. Wayne: Proposition E. In the resizing array implementation of Stack (Algorithm 1.1), the average number of array ...
72 views

### In Amortized Analysis, can we chose how big $n$ is?

Suppose I want to show by contradiction that the amortized cost of a data structure with some operations cannot be less then $\Theta(k)$. I assume for the sake of contradiction that it is possible. ...
395 views

### Amortized time of insertion into an Array list

According to Amortized time cost of insertion into an Array list, A dynamically resizing array list will resize when the number of elements reaches a power of two. So, after n elements inserted, we'...
55 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 (...
I'm trying to prove that the amortized time complexity of appending to a dynamic array that resizes in accordance with capacity = $N$ to $N+\lceil{\frac{N}{4}}\rceil$ is $O(1)$. I'm assuming that ...
Consider the follow operations on a stack of size at most $k$. Push - insert element in the stack - actual cost 1 Pop - remove top element from the stack - actual cost 1 Copy - copy whole stack (...