Question

Determine Theta for the following code fragments in the average case. Explain your answer.

1. a = b + c;

d = a + e;

2. sum = 0;

for (i=0; i<3; i++)

for (j=0; j

sum++;

3. sum = 0;

for (i=1; i<=n; i*=2)

for (j=1; j<=n; j++)

sum++;

4. Assume that array A contains n values, Random takes constant time,

and sort takes n log n steps.

for (i=0; i

for (j=0; j

A[j] = Random(n);

sort(A, n);

5. Assume array A contains a random permutation of the values from 0 to n - 1.

sum = 0;

for (i=0; i

for (j=0; A[j]!=i; j++)

sum++;

Answer 1

1. sum = 0;

for (i=0; i<3; i++)

for (j=0; j<n;j++)

sum++;

The first loop runs for 3 times. and the secondd one for n times after which 1 operation is done so total operations =3n and

3.

sum = 0;

for (i=1; i<=n; i*=2)

for (j=1; j<=n; j++)

sum++;

In first loop i starts from 1 and doubles itself in every iteraion so it runs for log(n) many times.

and for each iteration of i the inner loop runs for n time inside which 1 operation is done so total operations is nlog(n) and

4.

for (i=0; i<n;i++)

for (j=0; j<n:i++)

A[j] = Random(n);

sort(A, n);

sort(A, n); The first 3 line takes n^2 much time since i runs for n iteration and j runs for n iterations and constant operation(Random) is done. After that sort takes nlogn so

5

sum = 0;

for (i=0; i<n;i++)

for (j=0; A[j]!=i; j++)

sum++;

In best case scenarion when A=[0,1,2,....n-1]

when i=0 second loop runs for 1 time

when i=1 second loop runs for 2 time

when i=2 second loop runs for 3 time

...

so total operations=

in every other case the number of operations exceeds the best case