4
$\begingroup$

Several (tutoring) students have asked me for a formal definition of amortized time and I've never been able to find one online. All the literature I've found usually outlines the three most common methods for doing the actual analysis and no more. In a few places there are explanations of why the amortized time for $op$ is not $O(f(n))$ by presenting a series of operations whose combined $op$s take $\omega(f(n))$ on average, but nowhere I've looked provides an unambiguous definition.

The definition I've settled on is:

For some data structure $S$ and operation $op$ of $S$, the amortized time for $op$ is $O(f(n))$ if and only if for every sufficiently large $m$ and any series of $m$ operations on $S$, if $k$ of those operations were $op$ then the sum of actual times for those $k$ operations in the series is $O(k\cdot f(n))$.

The amortized time for $op$ is $\Omega(f(n))$ if and only if there exists such a series where the sum of actual times of the $op$s is $\Omega(f(n))$.

The above can be applied to $o(f(n))$ and $\omega(f(n))$ respectively.

My question is whether this is a good definition of amortized time for operations in a data structure and if not, what would a better definition be?

$\endgroup$
0
4
$\begingroup$

Consider a data structure with operations $o_1,\ldots,o_k$. We say that these operations have amortized time $t_1,\ldots,t_k$ if any sequence of operations which contains $m_i$ operations of type $o_i$ runs in time at most $\sum_i m_i t_i$. This is essentially the same definition as yours, in a more general setting.

We often allow $t_1,\ldots,t_m$ to depend on some promise on the data structure. One common example is $t_1,\ldots,t_m$ being a function of $n$, where $n$ is a bound on the total number of elements in the data structure. We will consider this example as we go on.

If there is only one operation $x$, then its amortized time is $\Omega(s(n))$ if whenever $t(n)$ is a valid amortized time for $x(n)$, $t(n) = \Omega(s(n))$. This can be proved by exhibiting, for each $n$, a sequence of $m$ operations, maintaining the promise on the data structure, which take time $\Omega(m s(n))$. Sometimes we want to prove such lower bounds for every implementation of an abstract data structure. The amortized time is $\Omega(s(n))$ if it is $\Omega(s(n))$ in any valid implementation of the ADT.

If there is more than one operation, then it's more difficult to talk about amortized time lower bounds, since now we're dealing with asymptotics of several operations at once. When dealing with concrete data structures, you can show, for example, that $t_1(n),\ldots,t_k(n)$ is a valid amortized time, but if you replace a single $t_i(n)$ (or perhaps all of them) by a function which is $o(t_i(n))$, then you don't get a valid amortized time.

For abstract data structures, you can prove lower bounds on individual operations, as well as tradeoffs. One example is a statement of the form $t_1(n) = \Omega(s_1(n))$ or $t_2(n) = \Omega(s_2(n))$. Another is a statement of the form $t_1(n) t_2(n) = \Omega(s(n))$.

$\endgroup$

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.