Timeline for If x operations cost O(x) amortized then how much xy operations cost?
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 23, 2017 at 12:37 | history | edited | CommunityBot |
replaced http://stackoverflow.com/ with https://stackoverflow.com/
|
|
| Aug 23, 2014 at 18:00 | vote | accept | Alaa M. | ||
| Aug 4, 2014 at 14:44 | comment | added | Lurr | You may also look in reverse if you got $O(x^2y)$ (worst time) complexity while testing algorithm for some different big $y$ you will calculate amortized time of $x$ operations as $O(x^2)$ not $O(x)$ for worst case even if you have better performance in average and average probabilistic complexity will be $O(x)$. Amortized and worst case are not opposites, opposites are worst case and best case and you can calculate amortized for both of them. | |
| Aug 4, 2014 at 14:32 | comment | added | Lurr | 1 operation can take $O(x)$ or even $O(xy)$ but not all or any sufficient number operations if there are many of them. Look for typical dynamic array example, any operation is $O(1)$ amortized but can take $O(n)$ time, but if we have $n$ operations where $n$ bigger than initial length we have granted $O(n)$ time complexity for all of them. | |
| Aug 4, 2014 at 14:08 | comment | added | Alaa M. | OK now i understand what you're trying to say. But why $O(xy)$ worst case if 1 operation could take $O(x)$ time worst case?! I'd say $O(xy)$ amortized and not worst case. | |
| Aug 4, 2014 at 0:55 | comment | added | Lurr | I tried to correct my English, but it seems it's all I can do, if you understand what amortized is I have no idea what do you not understand. Sorry. | |
| Aug 4, 2014 at 0:50 | history | edited | Lurr | CC BY-SA 3.0 |
spelling
|
| Aug 4, 2014 at 0:36 | comment | added | Alaa M. | I didn't understand what you're trying to say. Please correct your English if you can. Anyway, I guess you're just trying to explain what Amortized Analysis is. If so, please read my comment above which shows that i understand what it is. My question is how come it will perform $xy$ operations in $O(xy)$ w.c ? I think it may perform 1 operation in $O(xy)$ or $O(x)$ w.c. But $O(xy)$ amortized | |
| Aug 4, 2014 at 0:05 | history | edited | Lurr | CC BY-SA 3.0 |
spelling
|
| Aug 3, 2014 at 23:46 | review | First posts | |||
| Aug 4, 2014 at 2:46 | |||||
| Aug 3, 2014 at 23:44 | history | answered | Lurr | CC BY-SA 3.0 |