376 views
1 votes
1 votes

Consider the following data structure: Usually, inserting an element to this datastructure requires \Theta(1) work. However, the data-structure has a parameter k, s.t. every k elements we insert, it requires additional \Theta(k) work. That is, upon insertion of the k-th element, 2k-th element, 3k-th element and so on, we take additional \Theta(k) steps. What is the amortized cost per operation of inserting k^{33} elements into the data structure?

(a) \Theta(1)

(b) \Theta(\sqrt{k})

(c)\Theta(k)

(d) \Theta(k^{33})

1 Answer

1 votes
1 votes

EDIT:

As upon insertion of the k-th element, 2k-th element, 3k-th element and so on, we take additional \Theta(k) steps. 

So for insertion of K^33 elements no of sets of (k) elements:

k+k+k+.......................... +k (n terms)= k^33

k*n=k^33 => n=k^32

As given each set of k insertion takes \Theta(k) steps . 

So total cost of insertion for k^33 elements= no of set of k insertion * cost per set insertion = k^32 * k = \Theta(k^{33})

so cost per operation = \Theta(1)

so ans should be option (a)

edited by

Related questions

0 votes
0 votes
2 answers
2
Pranabesh Ghosh 1 asked Aug 30, 2016
553 views
Given an array of integers what is the worst case time complexity that would find pair of integers which are same?A) O(nlogn)B) O(n)C) O()D) O(nloglogn)
4 votes
4 votes
1 answer
3
Pranabesh Ghosh 1 asked Aug 30, 2016
672 views
A min heap with 1000 elements is stored in an array. What is the maximum possible index number for 9th min element?A) 254B) 100C) 9D) 511
2 votes
2 votes
1 answer
4
Pranabesh Ghosh 1 asked Aug 30, 2016
738 views
Suppose that an application have a huge number of insert operations, but only few delete max operations. Which priority-queue implementation would be most effective:A) Ma...