What is the amortized complexity of inserting n elements into a dynamic array us

Question

What is the amortized complexity of inserting n elements into a dynamic array using the following c++ code. Assume the array is empty.

int current_size = 0;
int limit = 0;
doubel* array = 0;

void Add_Array::(int n)
   if (current_size == limit)
   {
   if (array == 0)
{
   array_limit += 1;
   array = new double[limit];
   }
else
{
double* copy_array = new double[limit * 2];
for (int i = 0; i < limit; i++)
{
copy_array[i] = array[i];
}
   delete[] array;
   array = copy_array;
   array_limit *= 2;
}
array[current_size] = n;
current_size += 1;
}

Explanation / Answer

If we use simple analysis, the worst case cost of an insertion is O(n). Therefore, worst case cost of n inserts is n * O(n) which is O(n2). This analysis gives an upper bound, but not a tight upper bound for n insertions as all insertions don’t take (n) time.

Item No: 1 2 3 4 5 6 7 8 9 10 ......

Table Size: 1 2 4 4 8 8 8 8 16 16 ......

cost: 1 2 3 1 5 1 1 1 9 1 ...

Amoratized Cost =(1+2+3+4+5+1+1+9+1...) / n

We can simplify the above series by breaking terms 2,3,5,9.. int two as (1+1), (1+2), (1+4),(1+8)

Amortized Cost =[ (1+1+1+1...) + (1+2+4+....) ] / n

<=[n+2n] / n

<=3

Amortized Cost = O(1).

So using Amortized Analysis, we could prove that the Dynamic Table scheme has O(1) insertion time which is a great result used in hashing.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.