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 = 3size/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;

}

Question

Computers & Technology

River Grant

30 April, 18:25

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 = 3size/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;

}

+4

Answers (1)

Know the Answer?

Donavan Ross · Answer 1

The complexity will be O ((3/2) ^N).

Explanation:

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.