Questions tagged [amortized-analysis]

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

Filter by
Sorted by
Tagged with
47
votes
9answers
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: ...
26
votes
2answers
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 ...
24
votes
2answers
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 ...
11
votes
1answer
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$-...
10
votes
1answer
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 ...
7
votes
4answers
1k views

Questions about amortised analysis

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 ...
7
votes
1answer
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 ...
6
votes
1answer
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 ...
6
votes
1answer
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 "...
6
votes
1answer
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 ...
6
votes
2answers
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 ...
6
votes
0answers
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?
5
votes
2answers
1k views

Advantages of amortized analysis

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 ...
5
votes
1answer
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 ...
5
votes
1answer
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 ...
5
votes
1answer
2k views

Why is the path compression (no rank) for disjoint sets $O(\log n)$ amortized for Find-Set?

I was trying to understand why using only path compression (no rank) would yield $m log(n) $ total run time for a sequence of $m$ operations for Find-Set. I was told that the potential function: $$ \...
5
votes
1answer
621 views

Find amortized cost for insertion in binary arrays using accounting/potential methods?

Background: The idea of this data structure is as follows. We will have a collection of arrays, where array $i$ has size $2^i$. Each array is either empty or full, and each is in sorted order. ...
5
votes
1answer
1k views

How to compute amoritized cost for a dynamic array?

I am trying to understand how to do the amortized cost for a dynamic table. Suppose we are using the accounting method. Let A of size m be an array of n elements. When $n = m$, then we create a new ...
4
votes
1answer
762 views

Why do we need "potential” for amortized analysis?

In the current version as of the Wikipedia article “Potential method”, the amortized cost of each operation is defined as the following $$ T_{\mathrm{amortized}}(o) = T_{\mathrm{actual}}(o) + C \cdot (...
4
votes
1answer
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, ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
2answers
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
3
votes
2answers
775 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$ ...
3
votes
0answers
972 views

Analysis of Weighted Quick Union with Path Compression

I have searched the internet for an analysis of why WQUPC is amortized $O( m \alpha (n) ) $ for m operations on n nodes ( $\alpha ( n) $ is the inverse Ackerman function). I understand why it is $O ( ...
2
votes
2answers
173 views

Constant factor of an array

In Elements of Programming Interviews in Python by Aziz, Lee and Prakash, they state on page 41: Insertion into a full array can be handled by resizing, i.e., allocating a new array with ...
2
votes
2answers
2k views

Creating a binomial heap from an array in Θ(n) time

I'm studying binomial heaps. A book tells me that insertion of a node to a binomial heap take $\Theta(\log n)$ time. So given an array of $n$ elements it would take $\Theta(n \log n)$ time to convert ...
2
votes
2answers
773 views

Sequence of N operations Amortized Analysis

A sequence of $N$ operations is performed on a certain data structure. The $i$-th operation costs $i$ if $i$ is a power of 2, else it costs 1. How can I calculate the amortized cost for every ...
2
votes
1answer
140 views

Binary heap removal peculiar potential function analysis [closed]

Given the potential function $\phi$, it seems that remove max may take $O(1)$ amoratized, meaning that $n$ removals would take $O(n)$, which can't be, as it means we get a linear time comparison based ...
2
votes
2answers
269 views

Amortized analysis of max-heap

Consider an ordinary binary max-heap data structure with $n$ elements that supports insert and extract-max in $O(\log n)$ worst-case time. Question: If extract max is $O(1)$ amortized does that ...
2
votes
1answer
75 views

Why does the total credit associated with a data structure must be nonnegative at all times for the accounting method?

I was reading CLRS and it said in the chapter for the accounting method (for amortized analysis): the total credit associated with the data the structure must be nonnegative at all times. where ...
2
votes
1answer
107 views

array with a twist

Imagine that we have an array like structure A with n elements all of which are initially 0. ($A[i]=0$) What is a data structure that supports the following operations: 1) Given an element A[i]=0 ...
2
votes
1answer
1k views

Basics of Amortised Analysis

I cannot really find a source that does not use the same examples provided by CLRS. I need a simpler example than MULTI-POP example. Could someone provide an ...
2
votes
1answer
388 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 ...
2
votes
1answer
2k views

How does the token method of amortized analysis work in this example?

Below is the description of the answer to a question which says the following: Design a data structure to support two operations for a dynamic multiset S of integers which allows duplicate values. ...
2
votes
1answer
2k views

Amortize time for a counter with the operations INCREMENT and DECREMENT

Let a binary counter with the operations INCREMENT and DECREMENT. I need to show that you can't implement this kind of counter with constant amortized time per operation. Hence, I need to show ...
2
votes
2answers
218 views

Amortized Analysis for Addition of $n$ numbers

How can we add n positive integers with binary expansion $l_1$, $l_2$,...$l_n$ bits so that the total complexity is $O (\sum l_i)$ for $i = {1,...,n}$ ? More importantly, how can show this complexity ...
2
votes
1answer
1k views

Finding farthest item in an array with duplicates

I have an array $A[]$ of size $L$, which contains numbers in the range $1 \ldots N$. Here $L>N$, so the array will contain repetitions. If $x,y$ are two numbers that are both present in the array,...
2
votes
0answers
45 views

Algorithm to optimize redistribution of balls amongst urns [closed]

Here is the question: Say we have k urns with 1 ball in each urn. At each iteration of the game, I pick one urn and redistribute its contents amongst other urns and each urn can receive at most one ...
2
votes
0answers
70 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 ...
2
votes
0answers
228 views

Amortized time complexity of append on a dynamic array that resizes according to geometric base 1.25?

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 ...
2
votes
0answers
96 views

Array counter with mimimum find

I need to implement data strucure such as array, but with the following interface: GetMin() - Returns the minimum from the array IncRight(index) - Increases all values from specified index to the end ...
2
votes
0answers
132 views

How to compute amortized complexity of n runs of Dijkstra's algorithm?

I'm trying to figure out how to compute an amortized complexity/ or complexity of this algorithm. We have a Graph which is oriented. And we are going to run Dijkstra's algorithm for finding a shortest ...
2
votes
0answers
98 views

What is hiding behind amortized constant delay enumeration?

The following may contain errors. It is precisely because I am not sure I understand the topic that I am asking questions. I do not have books about it and could not find an adequate reference on the ...
1
vote
2answers
148 views

What does $O(\alpha(n))$ amortized time mean?

DELETE(S, i): Delete integer $i$ from the set $S$. if $i \notin S$, there is no effect. from a set of consectutive integers like $S = \{1,2,3,5,6\}$ Provide a data structure and an algorithm for ...
1
vote
2answers
291 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 ...