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
1
vote
0answers
13 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 ...
3
votes
2answers
744 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$ ...
0
votes
1answer
54 views

What time complexity is more significant? [closed]

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 ...
1
vote
1answer
170 views

Amortized analysis - increment in ternary counter [closed]

What is the amortized analysis of increment action in a ternary counter that is initialized to 0?
1
vote
2answers
271 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 ...
0
votes
0answers
29 views

Splay tree amortized cost analysis

I am looking into the amortized analysis of splay trees and seem to be missing something. Pretty much every resource uses the accounting method which I believe I grasp. What confuses me is the part ...
0
votes
1answer
43 views

Best known (state of science) time complexity of an array access problem

Consider an Array $A$ with $n$ values and the following operations: get(i): Returns the value of $A[i]$ insert (x): Insert the element x into the any free place in A (not necessarily in $A[x]$ or the ...
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
2answers
168 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 ...
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 ...
0
votes
1answer
120 views

How to do if a potential function Does not work? Amortized analysis

Here is an example taken from CLRS. q)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 ...
1
vote
1answer
174 views

general question amortized cost and worst case

lets say a data structure has operations called insert and delete both of which take O(log(n)) worst case. Suppose the amortized cost of insert is O(log(n)) and the amortized cost of delete is O(1). ...
7
votes
1answer
480 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 ...
0
votes
0answers
77 views

if binary heap potential function is c*size(binary heap)) then insert will not take O(logn)and extract min will not take O(1) amortized time

So i want to prove that if i choose a potential function for binary heap as any constant*size of the binary heap (n is the number of nodes) then my insert will not have O(logn) amortized cost and ...
1
vote
2answers
139 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 ...
2
votes
2answers
261 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 ...
1
vote
1answer
166 views

amortized analysis of max heap

Q) Consider an ordinary binary max-heap data structure with n elements that supports insert and extract-max in $O(log(n))$ worst-case time. Give a potential function $\Phi$ such that the amortized ...
1
vote
1answer
105 views

Amortized time complexity for double stack emulated queue

Assume that we have a data type $stack$ which has two operation $push$ and $pop$, both operations' time complexity is $O(1)$ in worst case. The $stack$ also has a property $size$ indicate how many ...
0
votes
1answer
67 views

The validity of the potential function for splay tree

The paper "Self-Adjusting Binary Search Trees" defines (Page 658) the potential function for analyzing the amortized cost of a sequence of $m$ splay operations as the sum of the ranks of all nodes in ...
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: ...
1
vote
0answers
126 views

Sequence of operations of Union-Find of length $m$ ($n$ being the number of Make-Set operations) with time complexity in $\Omega(m\log n)$

In Union-Find with link-by-rank but no path compression find a sequence of operations Make-Set, Find, Union of length $m$, containing $n$ Make-Set operations, and with time complexity in $\Omega(m\log ...
2
votes
1answer
383 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
0answers
69 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 ...
1
vote
0answers
338 views

Accounting method vs Potential method for analysing an augmented stack and differences with standard complexity analysis

With reference to chapter 17 of CLRS, (Amortized analysis). I'm trying to understand the differences between the accounting method and the potential method. Let's start with standard analysis of the ...
0
votes
1answer
332 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'...
1
vote
1answer
354 views

The Potential function for Fibonacci heaps

I am trying to get a better understanding of Fibonacci Heaps. I noticed the following definition for the potential function. $$ \Phi(F)=|W| +2\cdot \text{# marks}. $$ I do not understand why it is ...
3
votes
0answers
967 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
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 ...
0
votes
1answer
80 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 ...
0
votes
1answer
467 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 ...
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 ...
0
votes
1answer
65 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. ...
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 ...
1
vote
0answers
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 (...
2
votes
0answers
226 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 ...
1
vote
2answers
287 views

Potential function for stack problem

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

How to compare an experimental study with amortized times

I have an implementation of a data structure I have to study for a group project (Fibonacci heaps if you're interested). I'm asked to compare the theoretical results of the operations in amortized ...
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 ...
4
votes
1answer
746 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 (...
5
votes
1answer
613 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. ...
1
vote
1answer
2k views

Accounting method amortized analysis of a sequence of operations (CLRS 17.2-2)

I'm working through CLRS, Chapter 17 on Amortized Analysis. One of the problems I attempted to solve is 17.2-2 (described below), but my answer differs from the one in the instructor's manual, so I ...
0
votes
1answer
785 views

Amortized analysis for dynamic array - how to come up with a potential function?

I learned about amortized analysis and the potential method, I also leaned an example of a binary counter which I think I understand well. In the case of the binary counter I understand the choice of ...
1
vote
1answer
269 views

Height and depth of every node in Path Compression

If we have an union-find(disjoint-set) data structure and we are doing an union by rank and path compression for a find operation, how would the depth and height of every node change after the find ...
0
votes
0answers
217 views

Analysis of Union-Find(Disjoint Sets)

I have been trying to learn more about amortized analysis. Recently I came across the Disjoint Sets or Union-Find structures. I am using union by rank and path comparison. The potential of such data ...
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 ...
1
vote
0answers
36 views

Why is maximum size of root is 2n + 1 in Splay trees?

In the amortized analysis of Splaying in Dynamic trees, let us consider a splay tree $T$ with $n$ keys and $v$ be a node of $T$. We define $size(v)$ as the number of nodes in the subtree rooted at $...
1
vote
1answer
35 views

Is the potential difference in the two consecutive states of a data structure equal to the credit of the change inducing operation?

I am following CLRS for studying Amortized analysis with potential function and there I came through the following : Let a data structure go through states : $D_0 $ $D_1$ $D_2$ $ ....$ $D_n$ while ...
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
212 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), ...
-1
votes
1answer
349 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 ...