# Questions tagged [amortized-analysis]

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

99 questions
Filter by
Sorted by
Tagged with
11k views

### Does there exist a priority queue with $O(1)$ extracts?

There are a great many data structures that implement the priority-queue interface: Insert: insert an element into the structure Get-Min: return the smallest element in the structure Extract-Min: ...
5k views

### Data structure with search, insert and delete in amortised time $O(1)$?

Is there a data structure to maintain an ordered list that supports the following operations in $O(1)$ amortized time? GetElement(k): Return the $k$th element of the list. InsertAfter(x,y): Insert ...
22k 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 ...
279 views

### Can an NP-hard problem be polynomial on average?

I'm wondering if there are any $NP$-hard problems which are polynomial" in the average case. I think there are two ways to interpret this? If $P \neq NP$, can there be an algorithm solving an $NP$-...
6k views

### Potential function binary heap extract max O(1)

I need help figuring the potential function for a max heap so that extract max is completed in $O(1)$ amortised time. I should add that I do not have a good understanding of the potential method. I ...
1k views

As a preperation of an exam about algorithms and complexity, I am currently solving old exercises. One concept I have already been struggling with when I encountered it for the first time is the ...
495 views

### Incremental strongly connected components

For a changing directed graph, I would like to maintain information about strongly connected components. The graph operations are incremental: only vertex addition and edge addition. What data ...
4k views

### 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've resized at sizes 1, 2, 4, ... , n. This also means we've copied ...
4k views

### What is the intuition behind the Potential Function in Amortized Analysis of some algorithm?

I have come across many amortized analysis using a potential function. They all look magical to me. Everything works perfectly but I never got the intuition behind how they come up with such a "...
3k views

### How can I make sense of amortized accounting method?

Amortized accounting method has to be one of the most abstract analysis technique I have ever seen in my life (maybe aside from the potential method which I haven't read). In the example of the Stack ...
503 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 ...
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?
1k views

I understood what amortized analysis does, but can anyone tell me what is the main purpose of this kind of analysis? What I understood: Let say we have 3 three operations a,b,c used 1,2 and 3 times ...
1k views

### What is a clairvoyant algorithm?

When talking about general data structure design, my lecture notes talk about one of the concerns being cost of operations. As well as the individual cost, it mentions amortized cost. But then it goes ...
3k 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 ...
2k views

3k views

### Potential method for dynamic binary search

I'm trying to solve 17-2(b) problem from Cormen(CLRS) using potential method. Problem from Cormen: 17-2 Making binary search dynamic Binary search of a sorted array takes logarithmic search time, ...
497 views

### Complexity of many constant time steps with occasional logarithmic steps

I have a data structure that can perform a task $T$ in constant time, $O(1)$. However, every $k$th invocation requires $O(\log{n})$, where $k$ is constant. Is it possible for this task to ever take ...
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 ...
707 views

### Does amortized complexity always equal to worst case complexity divided by n?

Is it true that given any operation that takes O(f(n)) amount of time, we do this n times in a process, then the amortized cost is O(f(n))/n? I'm confused because this statement is so simple and ...
3k views

### Amortised analysis of binary heap insert and delete-min

I'm trying to figure out how to do amortised analysis of heap insert and heap delete-min using potential function. We can assume, that insert is O(logn) and delete-min is O(logn) too. The goal is ...
118 views

### Where would someone find amortized analysis more useful than average analysis and the opposite?

I'm trying to understand the difference between these two. They both look at what happens on average, however amortized analysis is actually dealing with exactly the amount of operations you are doing ...
144 views

### Amortised analysis of a simple loop and 3 operations

I'm trying to figure out amortised analysis of this loop and I can't figure out how to prove that complexity is $O(n \log n)$. Operation OP(S,X[i]) has complexity ...
657 views

### Amortized analysis of base Fibonacci counter

We just started learning the potential method this week and I'm having a bit of trouble on this problem regarding Fibonacci numbers; specifically I'm having some difficulty thinking of a good ...
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$ ...