Question

1. Give the O-runtime depending on n for the code snippet below (n > 0).

for( j = n; j <= 0; j = j - 1)

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

                                                print(" ");

2. Give the O-runtime depending on n for the code snippet below (n > 0).

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

                                    for( k = 1; k <= n; k = k + 2)

                                                print(" ");

Answer 1

Answer 1:

O-runtime is O(1) for the code snippet below (n > 0).

for( j = n; j <= 0; j = j - 1) //STATEMENT 1

                                    for( k = 1; k <= n; k = k + 1) // STATEMENT 2

                                                print(" "); // STATEMENT 3

EXPLANATION :

The STATEMENT1 runs for no times. The value of j , it is initialised as j = n and the condition never becomes true because n > 0 ( given in question).

So, The inner statements ie. STATEMENT 2 , STATEMENT 3 then will not execute for any value of n,

Hence, the runtime complexity of above code is O( 1 ).

Answer 2. O-runtime depending is O ( n ² )   for the code snippet below (n > 0).

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

                                    for( k = 1; k <= n; k = k + 2) // STATEMENT 2

                                                print(" "); //STATEMENT 3

EXPLANATION :

The STATEMENT1 runs for n times ( from j=1 to j=n) , and STATEMENT2 runs for ( n / 2 ) times. And

STATEMENT3 runs constant time.

So, Correct Complexity is ( n * ( n / 2 ) ) = ( n² / 2 ) = n^{2 (} approx).

Hence, the O runtime of above code is O ( n² ) .