Question

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

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

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

Answer 1

Solution for the problem is provided below, please comment if any doubts:

1.

a)

Exact number of times execution of given statements in terms of n:

I. Statement 1

Answer: log₃(n)

Explanation:

• Here the statement 1 is inside a for loop and the for loop repeats from 1 to n, but the increment will be in powers of 3.
• That is the statement executs for i= 1, 3, 9, 27….n
• Thus total number of times = log₃(n)

II. Statement 2

Answer: n*(n-1)/2 , if x<5 and 0 times otherwise

Explanation:

• Here the statement 2 is inside two for loops, but it is inside a condition check “if(x<5)”.
• Thus if the condition “x<5” passes, it executs 1 time for i=1, 2 times for i=2,…
• Thus total number = 1+2+3+4+..n = n*(n-1)/2, surely zero if the conditionnot passed.

III. Statement 3

Answer: n(n+1)(n+2)/6 , if x>=5 and 0 times otherwise

Explanation:

• Here the statement 2 is inside two three “for” loops, but it is executes if condition check “if(x<5)” fails.
• Thus if the condition “x<5” not passes, it executs 1 time for i=1, 2 times for i=2,…
• The number of execution will be = 1+3+6+10+15…+= n(n+1)(n+2)/6

IV. Statement 4

III. Statement 3

Answer: (16^(logn)-1)/15

Explanation:

• Here the the statement is inside two “for” loops.
• The outer for loop will run on powers of 4 values of i.
  • 1, 4, 16,….
• The inner loop will execute as much time as that of first loop value.
• Thus total execution = 1*1+4*4+16*16…= 1+4²+4⁴…=(A geometric series of length log ₄n)=(16^(logn)-1)/15

b)

Big-O complexity of program segments:

I. Segment I

Answer: O(log(n))

Explanation:

• It contains only the statement 1 and the loops around it.
• Now the complexity will be execution complexity of statement 1,
• Which is O(log n).

II. Segment II

Answer: O(n³)

Explanation:

• It contains only statement 2 and 3 in serial execution.
• Thus the complexity will be higher order term.
• Which is O(n³)

III. Segment III

Answer: O(4^2logn)

Explanation:

• It will be the complexity of running time of statement 4.