Answer to Question #260079 in Algorithms for kriti

Question

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;

        } 

      } 

 }

Answer 1

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
        }
    }
}

$\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 $\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) = 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
        } 
    } 
}

$\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) = 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)$