Timeline for If x operations cost O(x) amortized then how much xy operations cost?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 23, 2014 at 18:00 | vote | accept | Alaa M. | ||
| Aug 3, 2014 at 23:44 | answer | added | Lurr | timeline score: 2 | |
| Aug 3, 2014 at 17:25 | history | edited | Raphael |
edited tags
|
|
| Aug 3, 2014 at 17:25 | comment | added | Raphael | Amortised != Expected. Also, what kind of sequences are we talking about here? In all cases I know, that does matter; we no longer anlayse the individual operations independently. | |
| Aug 3, 2014 at 15:25 | comment | added | Alaa M. | I know the definition... If an operation takes $O(n)$ w.c. then $n$ operations will take $O(n^2)$ w.c. and can take $O(n)$ amortized (e.g because the expensive operation occurs only after a long time... or it does something good for the data structure) | |
| Aug 3, 2014 at 15:21 | comment | added | D.W.♦ | Hint: start by looking at the definition of amortized complexity. | |
| Aug 3, 2014 at 15:01 | history | asked | Alaa M. | CC BY-SA 3.0 |