# Questions tagged [amortized-analysis]

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

134 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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, ...
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 ...
1 vote
45 views

1 vote
193 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 ...
767 views

### Why isn't the time complexity of constructing a Fenwick tree tighter than $O(n\lg n)$?

Intuition: Suppose I have an array of nonzero integer values $A[n]$ and a partially constructed Fenwick tree of this array: $F[k], n>k$. I can see why inserting the next element would be worst ...
74 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 ...
126 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. ...
312 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 ...
1 vote
127 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 ...
45 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) ...
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 ...
28k views

### Why is push_back in C++ vectors constant amortized?

I am learning C++ and noticed that the running time for the push_back function for vectors is constant "amortized." The documentation further notes that "If a reallocation happens, the reallocation is ...
125 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)$ ...
68 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 ...
565 views

### how to verify permutation generated in constant amortized time?

Here is an algorithm that generates the next permutation in lexicographic order, changing the given permutation in-place: Find the largest index k such that a[k] < a[k+1]. If no such index exists, ...
94 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 ...
104 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 ...
1k views

### Red-black tree amortized cost of the rebalancing

I've read in different sources that the amortized cost of a red-black tree rebalancing is constant (at least during the tree creation using only insertions). How can it be proven?
1 vote
128 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 ...
167 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)...
4k views

### What is the purpose of Mark field in Fibonacci Heaps?

In Fibonacci heaps, we keep a mark field for every node in the heap. Initially all the nodes are unmarked. Once a node is deleted, its parent is marked. If a node is deleted and its parent is already ...
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....
95 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]$...
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 ...
1 vote
134 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 ...
21 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 ...
3k views

### Can an algorithm with $\Theta(n^2)$ run time be faster than an algorithm with $\Theta(n\log n)$ run time?

This is a question posted for extra practice (i.e., not for credit): Can an algorithm with $\Theta(n^2)$ run time be faster than an algorithm with $\Theta(n\log n)$ run time? Explain. I'm not sure ...
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 ...
176 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)....
1 vote
537 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 ...
1 vote
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: <...
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 ...
2k 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$ ...
A certain algorithm executes $n$ operations of three types: insert, delete, and find. We know that $n/10$ of the operations are inserts, and the rest are deletes and finds. You are given two ...