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
51 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 ...
0
votes
0answers
18 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 ...
2
votes
3answers
546 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
0answers
37 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 ...
0
votes
1answer
57 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
1answer
30 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
1answer
54 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: <...
0
votes
0answers
18 views

The accounting Method analysis for table expansion by tripleling instead of doubling an array

If we double the array every time we get the amortized cost of 3n or 3$ if you prefer. I was wondering what would it be if we tripled the array size instead of doubling it. The rational between the ...
1
vote
0answers
14 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
915 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
58 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
428 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?
0
votes
0answers
31 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
44 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
48 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
181 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
500 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
144 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
207 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). ...
8
votes
1answer
602 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
79 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
184 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
283 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
180 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
145 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
73 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
137 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
429 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
82 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
408 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
367 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
371 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
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
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
86 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
557 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 ...
6
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
68 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
265 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
377 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
899 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
678 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
880 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
334 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 ...