Question

hi show your solution in full details not just the final answer ,cheers mate

can you help

please

thanks I am stuck please

Answer the following questions:

1. Given the code segments below with n as the problem size, answer the following questions:

//Code Segment 1 (Consider n as a power of 3)

int sum = 0;

for(int i = 1; i <= n; i = i*3)               
sum++;                                    // statement1

//Code Segment 2: (Consider both possibilities for x)

if(x < 5){

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

}

else{

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

           for(int j = 1; j <= i; j++)

                for(int k = 1; k <= j; k++)

         sum++;               // statement3

}

//Code Segment 3: Consider n as a power of 4.

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

1. (48 points) Find the exact number of times statement1, statement2, statement3 and statement4 get executed in terms of n.

(12 points) Determine the Big-O complexity of these 3 program fragments.

Answer 1

Answer:

//Code Segment 1 (Consider n as a power of 3)

int sum = 0;

for(int i = 1; i <= n; i = i*3)           (Time Complexity of a loop is considered as O(Logn) if the loop variables is divided / multiplied by a constant amount and here the loop variable is multiplied by 3.)
sum++;                                    // statement1 (So statement 1 is executed log₃n times and time complexity will be O(log₃n).)

//Code Segment 2: (Consider both possibilities for x)

if(x < 5){

    for(int i = 1; i <= n; i++) (Time Complexity of a loop is considered as O(n) if the loop variables is incremented / decremented by a constant amount. So this loop will run for n time.)
     for(int k = 1; k <= i; k++)   (This is inner loop and will run for n time because it will run till k<=i).
       sum++;                        // statement2 (So statement 2 is executed n*(n+1)/2 time and time complexity will be O(n*n).)

}

else{

     for(int i = 1; i <= n; i++) (This will run for O(n) time.)

           for(int j = 1; j <= i; j++) (This will run for O(n) time.)

                for(int k = 1; k <= j; k++)   (This will run for O(n) time.)

         sum++;               // statement3 (So statement 3 is executed n(n+1)(2n + 4)/12 times.and time complexity will be O(n*n*n).)

}

//Code Segment 3: Consider n as a power of 4.

for(int i = 1; i <= n; i = i*4)                      (Time Complexity of a loop is considered as O(Logn) if the loop variables is divided / multiplied by a constant amount and here the loop variable is multiplied by 4.)
for(int k = 1; k <= i; k++) (This will run for O(n) time, because of inner loop.)
sum++;                             // statement4 (So statement 4 is executed n * log₄n times and time complexity will be O(n*log₄n).)

Thus, we conclude that,

a)

Statement 1 is executed log₃n times.

Statement 2 is executed n*(n + 1)/2 times.

Statement 3 is executed n(n+1)(2n + 4)/12 times.

Statement 4 is executed n * log₄n times.

b)

Time complexity of code segment 1 is: O(log₃n).

Time complexity of code segment 2 is: O(n³).

Time complexity of code segment 3 is: O(n * log₄n).

Please give thumbsup, if you like it. Thanks.