Question #260079

Find out the step count for the following function using tabular method.

void ABC( int n ){    

     for( int i=1;  i<= n; i++){

         for (int j=1; j<=2^n;j=j*2)  { 

                     printf(“%d”,j);

                    

            }

    }

}

void Example2 (int n){

int a = 0;

for (int i = 0; i < N; i++) {

    for (int j = N; j > i; j--) {

               a = a + i + j;

        } 

      } 

 }



1
Expert's answer
2021-11-04T16:26:50-0400
void ABC( int n ){    
    for( int i=1;  i<= n; i++) {             // Step 1
        for (int j=1; j<=2^n;j=j*2)  {       // Step 2
            printf(“%d”,j);                  // Step 3
        }
    }
}

Step#CostFreq.Tot.costStep 1c1n+1c1(n+1)Step 2c2i=1n(n+1)c2n(n+1)Step 3c3i=1nnc3n2\begin{array}{|c||c|c|c|} \hline Step \# & Cost & Freq. & Tot. cost\\ \hline \text{Step 1} & c_1 & n+1 & c_1 \cdot(n+1) \\ \text{Step 2} & c_2 & \sum_{i=1}^{n}{(n+1)} & c_2 \cdot n \cdot (n+1) \\ \text{Step 3} & c_3 & \sum_{i=1}^{n}{n} & c_3 \cdot n^2 \\ \hline \end{array}

(The step 2 execute log2(2n)=n\text{log}_2(2^n) = n times and once more for checking exit conditions for every i) .

So total amount of steps is T(n)=c1(n+1)+c2n(n+1)+c3n2=(c2+c3)n2+(c1+c2)n+c1=O(n2)T(n) = c_1\cdot(n+1) + c_2\cdot n\cdot(n+1) + c_3 \cdot n^2 = (c_2+c_3)\cdot n^2 +(c_1+c_2)\cdot n + c_1 = O(n^2)


void Example2 (int n){
    int a = 0;                             // Step 1

    for (int i = 0; i < N; i++) {          // Step 2
        for (int j = N; j > i; j--) {      // Step 3
            a = a + i + j;                 // Step 4
        } 
    } 
}

Step#CostFreq.Tot.costStep 1c11c1Step 2c2n+1c2(n+1)Step 3c3i=1n(ni+1)c3(n+1)(n+2)/2Step 4c4i=1n(ni)c4n(n+1)/2\begin{array}{|c||c|c|c|} \hline Step \# & Cost & Freq. & Tot. cost \\ \hline \text{Step 1} & c_1 & 1 & c_1 \\ \text{Step 2} & c_2 & n +1 & c_2 \cdot (n+1) \\ \text{Step 3} & c_3 & \sum_{i=1}^{n}{(n-i+1)} & c_3 \cdot (n+1) \cdot (n +2)/2 \\ \text{Step 4} & c_4 & \sum_{i=1}^{n}{(n-i)} & c_4 \cdot n \cdot (n +1)/2 \\ \hline \end{array}

So total amount of steps is T(n)=c1+c2n+c3(n+1)(n+2)/2+c4n(n+1)/2=c3+c42n2+(c2+3c32+c42)n+(c1+c3+c42)=O(n2)T(n) = c_1 + c_2\cdot n + c_3 \cdot (n+1) \cdot (n +2)/2 + c_4 \cdot n \cdot (n +1)/2 = \frac{c_3+c_4}{2}\cdot n^2 +(c_2+\frac{3c_3}{2}+\frac{c_4}{2})\cdot n + (c_1+ c_3+\frac{c_4}{2}) = O(n^2)



Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!
LATEST TUTORIALS
APPROVED BY CLIENTS