Question

Suppose we perform a sequence of n operations on a data structure such that if some condition C(k) holds then the kth operation takes O(k) time, but otherwise, it only takes O(1) time.

For each condition C(k) listed below, determine the total time T(n) for the sequence of all n operations, and also the amortized time Tamortized(n) per each operation.
a) If C(k) is "k is a power of 2" then T(n)=O(n2) and Tamortized(n)=O(n).
b) If C(k) is "k is a multiple of 2" then T(n)=O(n3/2) and Tamortized(n)=O(n1/2).
c) If C(k) is "k is a perfect square" then T(n)=O(n3/2) and Tamortized(n)=O(n1/2).
d) If C(k) is "k is a multiple of 3" then T(n)=O(n4/3) and Tamortized(n)=O(n1/3).

Answer 1

b) If C(k) is "k is a multiple of 2" then T(n)=O(n3/2) and Tamortized(n)=O(n1/2).

Step-by-step explanation:

a) if C(k) is a power of 2 then kth operation takes k time.

So for 1, 2, 3, 4, 5,6,7,8,9 ... ..., n operations we need time for each operation 1,2,1,4,1,1,1,8,1,... ..., 2log n, if in worst case n is also a power of 2.

which gives 1+2+4+8+... ...+2log n+ (n-p), let say some p number of operations those took O(1) time

= 2log n+1-1+O(n)

=2 . 2log n-1+O(n)

=2n-1+O(n) [2 log n=n]

=O(n)

So the amortized cost of each operation = O(n)/n = O(1)

hence (a) can not be true.

option (b) is correct.

Now come to option (c ), given that if k is a multiple of 2, then kth operation takes k time

So the time taken by whole n operations = 2+4+6+... ...+n + (n-p), let say there are p number of operations taking O(1) time each, then

the total time taken = 2(1+2+3+... ...+n/2)+(n-p)

=2 . n/2(n/2+1)/2+(n-p)

=n/2(n/2+1)+O(n)

= O(n2)

And the amortized cost of each operation = O(n2)/n = O(n)

Hence the option (c) is not correct.

And for option (d) the analysis is same as (c)

the total time taken = 3(1+2+3+... ...+n/2)+(n-p)

=3 . n/2(n/2+1)/2+(n-p)

=3/2 . n/2(n/2+1)+O(n)

= O(n2)

And the amortized cost of each operation = O(n2)/n = O(n)

Hence the option (b) is not correct.