Skip to main content
edited tags
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393
Source Link
Alaa M.
  • 201
  • 1
  • 6

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?