0
$\begingroup$

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$ operations in $O(x)$ amortized means $O(1)$ expected time for $1$ operation. Then for $xy$ operations it'd be $O(xy)$ amortized (and I think $O(x^2y)$ worst case). Therefore, the statement is incorrect.

But the answers sheet says i'm wrong. Why?

$\endgroup$
  • $\begingroup$ Hint: start by looking at the definition of amortized complexity. $\endgroup$ – D.W. Aug 3 '14 at 15:21
  • $\begingroup$ 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) $\endgroup$ – Alaa M. Aug 3 '14 at 15:25
  • $\begingroup$ 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. $\endgroup$ – Raphael Aug 3 '14 at 17:25
2
$\begingroup$

Amortized is not just probabilistic, it means that for some big enough $y$, $xy$ operations can't take a long time and will guaranteed to be $O(x)$ in average in worst case (and therefore $O(xy)$ for all $xy$ operations), even through some of operations may take even $O(xy)$ time itself.

https://stackoverflow.com/questions/200384/constant-amortized-time

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Alaa M. Aug 4 '14 at 0:36
  • $\begingroup$ 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. $\endgroup$ – Lurr Aug 4 '14 at 0:55
  • $\begingroup$ 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. $\endgroup$ – Alaa M. Aug 4 '14 at 14:08
  • $\begingroup$ 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. $\endgroup$ – Lurr Aug 4 '14 at 14:32
  • $\begingroup$ 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. $\endgroup$ – Lurr Aug 4 '14 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.