A method in analysis of algorithms that considers the overall cost of a sequence of operations.
0
votes
0answers
53 views
Question about amortized analysis
Consider a dynamic table, where it expands when you fill a certain amount, and contracts when there is small enough elements.
Let $e$ be an arbitrary function which is the constraint to expand.
Let ...
1
vote
0answers
20 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
38 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
20 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, ...
3
votes
1answer
103 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 ...
7
votes
2answers
227 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 ...
6
votes
4answers
176 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 ...
5
votes
1answer
143 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 ...
2
votes
1answer
85 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
2answers
184 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 ...
9
votes
2answers
883 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 ...
23
votes
9answers
2k 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: ...
