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?

Improve this question
$\endgroup$
3
  • $\begingroup$ Hint: start by looking at the definition of amortized complexity. $\endgroup$
    – D.W. ♦
    Commented Aug 3, 2014 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.
    Commented Aug 3, 2014 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
    Commented Aug 3, 2014 at 17:25

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
5
  • $\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.
    Commented Aug 4, 2014 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
    Commented Aug 4, 2014 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.
    Commented Aug 4, 2014 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
    Commented Aug 4, 2014 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
    Commented Aug 4, 2014 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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