specified the code segment below and that n

Question

Specified  the code segment below and that n is the problem size, answer the following queries:

 

// . . .

int sum = 0;

if(x > 12){

for(int i = 1; i <= n; i = i * 2)
    for( intk = 0; k< n * n; k++)
        sum++;                        // statement1

}

else{

 

for(int i = 1; i <=n; i++)
           sum++;                          // statement2

}

 

 

for(int i = 1; i <= n; i = i +4)
    sum++;                                 // statement3

 

for(int i = 1; i <= n; i++)
    for( intk = 1; k<= n; k = k * 2)
        sum++;                              // statement4

 

1. Determine the exact number of times statement1, statement2, statement3 and statement4 get implemented.
2. Explain the Big-Q complexity of this program fragment in the best case. You must display the details of your computations and state the Big-Qrules that are used in the computations.
3. Explain the Big-Q complexity of this program fragment in the worst case. You must display the details of your computations and state the Big-Q rules that are used in the computations.