# If x operations cost O(x) amortized then how much xy operations cost?

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?

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

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