In Big-Θ notation, analyze the running time of the following pieces of code/pseudo-code. Describe the running time as a function of the input size (here, n)
int *a = new int [10]; // new is O(1)
int size = 10;
for (int i = 0; i < n; i ++)
{
if (i == size)
{
int newsize = 3*size/2;
int *b = new int [newsize]; // new is O(1)
for (int j = 0; j < size; j ++) b[j] = a[j];
delete [] a; // delete is O(1)
a = b;
size = newsize;
}
a[i] = i*i;
}
Notice that, in each step we do size operations and our size will gets multiplied by 3/2. If we do this N times, in total roughly we will do (3/2)^(N+1) operations.
