Search type Search syntax
Tags [tag]
Exact "words here"
Author user:1234
user:me (yours)
Score score:3 (3+)
score:0 (none)
Answers answers:3 (3+)
answers:0 (none)
isaccepted:yes
hasaccepted:no
inquestion:1234
Views views:250
Sections title:apples
body:"apples oranges"
URL url:"*.example.com"
Favorites infavorites:mine
infavorites:1234
Status closed:yes
duplicate:no
migrated:no
wiki:no
Types is:question
is:answer
Exclude -[tag]
-apples
For more details on advanced search visit our help page
Results tagged with Search options answers only user 683

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

1
vote
Let's review the potential function method. Suppose that the $i$th operation costs $c_i$ and the value of the potential function at time $i$ is $\Phi_i \geq 0$, and that $\Phi_0 = 0$ (the potential at …
answered Sep 3 '15 by Yuval Filmus
2
votes
What they mean is exactly that: the invariant maintained by the data structure is that each of the arrays $A_0,\ldots,A_{k-1}$ is sorted. Nothing is maintained regarding the relative order of elements …
answered Feb 27 '16 by Yuval Filmus
6
votes
No, if all we know about an operation is that it takes $O(f(n))$ times, then its amortized time is also $O(f(n))$. Sometimes, however, it is the case that while the worst-case running time is $O(f(n)) …
answered Dec 17 '14 by Yuval Filmus
2
votes
In the potential method, operation $O$, which has real cost (say time complexity) $p(O)$ is charged $c(O)$. The potential at any given point is $$\sum_{t=1}^T (c(O_t) - p(O_t)),$$ where $O_1,\ldots,O_ …
answered Nov 25 '15 by Yuval Filmus
1
vote
A reasonable potential function here would be $C\ell$ or $C(k-\ell)$, where $\ell$ is the number of elements on the stack. However, I don't think that the amortized cost can be bounded. Consider $k$ …
answered Mar 28 '17 by Yuval Filmus
2
votes
The potential function is a fictitious quantity which is used to bound the cost of operations in a data structure. Suppose that our data structure supports only one operation, whose worst-case cost is …
answered Sep 5 '16 by Yuval Filmus
4
votes
As is unfortunately sometimes the case, Wikipedia is doing a terrible job of explaining what amortized analysis actually is. The idea of amortized analysis is that while operations may have a bad wor …
answered Dec 13 '16 by Yuval Filmus
1
vote
You should be slightly more careful in your argument. Let the actual numbers you are adding be $x_1,\ldots,x_n > 0$, where $\ell_i = \lfloor \log_2 x_i \rfloor + 1$. The complexity of adding two numbe …
answered Mar 26 '14 by Yuval Filmus
1
vote
For a number $m$, let $\alpha(m) = \max \{ k : k! | m \}$. This sequence starts at $\infty,1,2,1,2,1,3,\ldots$. I claim that in iteration $t$ of the algorithm (where $1 \leq t \leq n!-1$), we have $n- …
answered Sep 25 '14 by Yuval Filmus
8
votes
If every $k$th operation takes $O(\log n)$ time, then the best bound you can get on the amortized complexity is $O(1 + \frac{\log n}{k})$. This follows from the definition of amortized complexity.
answered Apr 14 by Yuval Filmus
2
votes
We can divide the running time into several parts: Pushes. Pops. The first OP performed at every round. Subsequent OPs performed at every round. Note that every OP costs $O(\log n)$, that there ar …
answered Jun 14 '16 by Yuval Filmus
1
vote
The answer hinges on the definition of amortized cost. Since you haven't given such a definition, let me assume that you are using the common definition. Consider a data structure supporting operatio …
answered Mar 23 by Yuval Filmus
1
vote
Hint: Think of a value $n$ such that the transition from $n$ to $n+1$ and back is very costly.
answered Mar 10 '14 by Yuval Filmus
1
vote
What am I doing wrong here? You're using the wrong potential function. Keep looking. If you want to know the solution, the Wikipedia page on the potential method contains the answer.
answered Dec 5 '14 by Yuval Filmus
3
votes
Here is a solution using direct calculation (I never liked all the fancy methods). Consider the cost of the first $n$ inserts, and suppose that $2^k \leq n < 2^{k+1}$. Thus only the arrays $A_0,\ldots …
answered Nov 29 '16 by Yuval Filmus

15 30 50 per page