Question

3. Find the exact number of times (in terms of n) the innermost statement (X = X + 1) is executed in the following code. That is, find the final value of X. Then express the total running time in terms of O( ), Ω( ), or Θ( ) as appropriate.

X = 0;

for k = 1 to n

    for j = 1 to n – k

        X = X + 1;

4. The following program computes and returns (log2n), assuming the input n is an integer power of 2. That is, n=2j for some integer j ≥ 0.

int LOG (int n){

int m, k;

m = n;

k = 0;

while (m > 1) {

    m = m/2;

    k = k + 1; }

ruturn (k)

}

1. First, trace the execution of this program for a specific input value, n = 16. Tabulate the values of m and k at the beginning, just before the first execution of the while loop, and after each execution of the while loop.

2. Prove by induction that at the end of each execution of the while loop, the following relation holds between variables m and k. (This relation between the variables is called the loop invariant.)

m=n/2k

3. Then conclude that at the end, after the last iteration of the while loop, the program returns k=log2n

Answer 1

SOLUTION -

IF YOU HAVE ANY DOUBT PLEASE COMMENT DOWN BELOW I WILL SOLVE IT FOR YOU:)
----------------PLEASE RATE THE ANSWER-----------THANK YOU!!!!!!!!----------