Bruce Combs

Computers & Technology

26 November, 11:27

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 3" then T (n) - O (n4/) and Tamortized (n) O (n13).

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

c) If C (k) is "k is a perfect square" then T (n) O (n4/3) and Tamortized (n) = O (n13). O

d) If C (k) is "k is a multiple of 2" then T (n) = O (n2) and Tamortized (n) = O (n)