Timeline for Binary counter amortized analysis [closed]
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 12, 2014 at 9:25 | history | closed |
D.W.♦ vonbrand FrankW David Richerby Juho |
Needs details or clarity | |
| Mar 11, 2014 at 0:38 | review | Close votes | |||
| Mar 12, 2014 at 9:25 | |||||
| Mar 11, 2014 at 0:22 | comment | added | D.W.♦ | Hint: to make this kind of question better, include in the question what you've tried, what part you understand, what part you are having trouble with, and try to frame a specific question about your solution -- don't just paste the exercise and expect us to solve it for you. | |
| Mar 11, 2014 at 0:22 | comment | added | D.W.♦ | This is a dump of an exercise problem, not a question. If you have a specific question regarding the wording of the problem or concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See also here for our homework policy, and here for a relevant discussion. You may also want to check out our reference questions. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? | |
| Mar 10, 2014 at 12:13 | comment | added | Yuval Filmus | To clarify FrankW's comment, in your case the best that you can expect is for there to be some sequence of operations with amortized cost $\Theta(k)$. In contrast, if there are no decrements, then we have an amortized upper bound of $O(1)$ (which is the same as $\Theta(1)$), whatever the sequence of operations is. | |
| Mar 10, 2014 at 12:12 | answer | added | Yuval Filmus | timeline score: 1 | |
| Mar 10, 2014 at 11:34 | history | edited | David Richerby | CC BY-SA 3.0 |
Latexify, edit tags
|
| Mar 10, 2014 at 11:34 | history | suggested | FrankW | CC BY-SA 3.0 |
Latexify, edit tags
|
| Mar 10, 2014 at 11:33 | comment | added | FrankW | The $\Theta$-class does not hold. You can show (with amortized analysis), that the cost is ${\cal O}(n)$ (independent of $k$). (Since $\Omega(n)$ is a trivial lower bound, we get $\Theta(n)$. Furthermore it is easy to prove without amortized analysis, that ${\cal O}(n\cdot k)$ is an upper bound.) | |
| Mar 10, 2014 at 11:29 | review | Suggested edits | |||
| Mar 10, 2014 at 11:34 | |||||
| Mar 10, 2014 at 10:53 | history | edited | HaloKiller | CC BY-SA 3.0 |
edited title
|
| Mar 10, 2014 at 10:34 | history | asked | HaloKiller | CC BY-SA 3.0 |