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
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. ...
0
votes
0answers
237 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), ...
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
158 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 ...
-1
votes
1answer
387 views

What is the amortized time complexity of inserting an element to this heap?

Assume you implement a heap using an array and each time the array is full, you copy it to an array double its size. What is the amortized time complexity (for the worst case) of inserting elements ...
0
votes
0answers
202 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 ...
2
votes
0answers
139 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 ...
1
vote
0answers
89 views

Calculating the cost for each operation in amortized analysis

According to what I've read in the CLRS book , we calculate the amortized cost for a complete set , and not for a single operation.But in an exam question , it was asked about an operation amortized ...
3
votes
0answers
1k 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 ( ...
3
votes
1answer
669 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 ...
1
vote
1answer
50 views

What does it mean when each individual array is sorted in different array but bear no relationship to each other

There's a textbook problem that talks about making a binary search dynamic, then analyzing for its amortize cost. However I'm not exactly sure what is the organization scheme of this data structure. ...
1
vote
1answer
697 views

Reb-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 proved?
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: $$ \...
1
vote
0answers
44 views

Is it true that the potential method is usually the inverse of the accounting method in the context of amortized analysis?

I remember reading this somewhere (will post the source as soon as I find it), but was wondering, if anyone knows why this is true or has maybe an example to portray why this is the case.
2
votes
1answer
77 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 ...
-1
votes
1answer
74 views

Question regarding the potential method for amortized analysis [closed]

What does the following mean exactly for the potential method? Is this applicable to all situations? If the potential is positive, then we overcharged for some operations. If it is negative, we ...
0
votes
0answers
35 views

Time Complexity when loop variable depend upon outer loop variable [duplicate]

What is the time complexity of the following piece of code in worst case? ...
1
vote
1answer
5k views

give potential function - binary heap - extract-min in amortized const time and insert in log amortized time

Consider an ordinary binary min-heap data structure with n elements supporting the instructions INSERT and EXTRACT-MIN in O($\lg n)$ worst-case time. Give a potential function $\Phi$ such that the ...
1
vote
1answer
817 views

Amortized analysis for doubling resizing array is ~3n

I'm brushing up on stuff related to analysis of algorithms. And I have a question about this PDF I found. This is where I'm confused: Question 2: What if instead we decide to double the size of the ...
1
vote
1answer
2k views

Amortized analysis of binary counter with increment and resetting operations

I have a question about a specific amortized accounting algorithm and to be specific the variant with Reset operation. First, 9th line of increment sets $\max[A]$ to -1 if $i \le \max[A]$ because ...
1
vote
0answers
366 views

Potential method analysis for Insert and Extract-max on a Max heap data structure

Suppose that you do some sequence of operations on a max heap, in this case only Insert and Extract-max. Whenever the heap ...
6
votes
2answers
537 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 ...
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
2answers
808 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 ...
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?
1
vote
1answer
402 views

Amortized analysis of virtual, dynamic array using potential function

You often want to implement an array $A$ where the length fluctuates over time. If at some point $A$ has length $n$, then you would like to use space $O(n)$. Consider the following: At all moments, a ...
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 ...
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 ...
3
votes
1answer
120 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 ...
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 "...
1
vote
1answer
361 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, ...
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 ...
0
votes
1answer
71 views

If x operations cost O(x) amortized then how much xy operations cost?

True or False? Say some data structure can perform $x$ operations in amortized $O(x)$ time. Then for a big enough $y$ it can perform $xy$ operations in worst case $O(xy)$ time. My attempt: $x$ ...
11
votes
1answer
313 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$-...
2
votes
2answers
833 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
141 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
0answers
99 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 ...
2
votes
2answers
241 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 ...
-1
votes
1answer
282 views

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 ...
0
votes
1answer
991 views

Binary counter amortized analysis [closed]

This is a question I have stumbled upon in my textbook, and didn't really know how to approach: Given a $k$-bit binary counter. We have an operation Increment, which adds 1 to the counter. We add a ...
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 ...
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

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
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 ...
1
vote
0answers
52 views

Potential function in amortized analysis [duplicate]

I am trying to calculate the amortized cost of a dynamic array, that's size becomes 4 times the size when the array is filled. (when you re-size, you create a new one and copy the elements there). ...
1
vote
1answer
2k views

How to do amortized analysis for an expanding array? [duplicate]

If you have an array that expands when it is completely filled and the new size is N = N + 1 + ceiling(log2(N)) (N is the current size, and then N becomes the new ...
0
votes
0answers
69 views

amortized analysis accounting method [duplicate]

If you have a dynamic array where the size $s$ becomes $4s$ when you fill the array and there are no delete operations. How much do you spend per insert? I am asking because when the size doubles, ...
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 ...
24
votes
2answers
23k 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 ...
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 ...