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

learn more… | top users | synonyms

-1
votes
0answers
22 views

Amortized cost of increment counter problem

Consider the increment-counter problem, where now the counter is represented in base 10, the initial count is 0, and where the cost of an increment is the number of digits that change. (a) Show by ...
3
votes
1answer
32 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 ...
2
votes
1answer
40 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 ...
0
votes
1answer
49 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 ...
1
vote
1answer
79 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
40 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$ ...
9
votes
1answer
114 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 ...
0
votes
0answers
26 views

Amortized analysis of nested loop

I have a fairly simple algorithm, consisting of an inner while-loop in an outer for-loop. Even though the algorithm is simple enough, it's quite hard to explain exactly what it does. However, it's ...
2
votes
2answers
61 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
47 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
38 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
64 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
65 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
74 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
185 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
82 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
100 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 ...
0
votes
1answer
156 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
29 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
307 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
25 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
270 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 ...
11
votes
2answers
2k 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
336 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
1k 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
388 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
420 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 ...
14
votes
2answers
2k 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 ...
27
votes
9answers
3k 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: ...