Problem 3: Suppose we are maintaining a data structure under a series of n opera
ID: 3818210 • Letter: P
Question
Problem 3: Suppose we are maintaining a data structure under a series of n operations. Let
f(k) denote the actual running time of the kth operation. For each of the following functions f,
determine the resulting amortized cost of a single operation.
a) f (k) = n2 if k is a power of 2, and f (k) = 1 otherwise.
b) f (k) = k if k is a Fibonacci number, and f (k) = 1 otherwise.
c) Let T be a complete binary search tree, storing the integer keys 1 through n. f (k) is
the number of ancestors of node k.
Explanation / Answer
case 1:
For every n that is a power of two,double the size of a hash table and insert all items in the old table in to new table.
The amortized cost of a single insertion is $O(1)$ as the cost of n operations on the structure is $T(n)/n = 1$.
[ sum_{i=1}^n c_i leq n + sum_{j=0}^{lfloor log n floor} 2^j ]
[ < n + 2^{lfloor log n floor} +1 ]
[ = n + 2 * 2^{lfloor log n floor} ]
[leq n + 2n ]
[ = 3n ]
Case two:
if the same definition follows (From CLRS) that any sequence of $n$ operations on a structure takes $leq T(n)$ time, the amortized
time per operation is $T(n)/n$.
In this case, $T(n^2)/n = n$ and amortized cost of a single operation is $O(n)$.
case 1:
For every n that is a power of two,double the size of a hash table and insert all items in the old table in to new table.
The amortized cost of a single insertion is $O(1)$ as the cost of n operations on the structure is $T(n)/n = 1$.
[ sum_{i=1}^n c_i leq n + sum_{j=0}^{lfloor log n floor} 2^j ]
[ < n + 2^{lfloor log n floor} +1 ]
[ = n + 2 * 2^{lfloor log n floor} ]
[leq n + 2n ]
[ = 3n ]
Case two:
if the same definition follows (From CLRS) that any sequence of $n$ operations on a structure takes $leq T(n)$ time, the amortized
time per operation is $T(n)/n$.
In this case, $T(n^2)/n = n$ and amortized cost of a single operation is $O(n)$.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.