Question

Question1

if possible, could anyone do with explanation
For each of the following code snippets, give both of the following:
a. Give the overall T(n) run me analysis expression for the code.
b. Describe the worst case running me of the code snippet in Big‑Oh notation.

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

{

for (int j=0;j<n/2;j++)

{ sum++;}

}

2.void silly(int n,int x,int y)

{ for (int i=0;i<n/2;i++)

{ if (x<y)

{ for (int j=0;j<100*n*n;j++)

{ cout<< "j="<<j<<endl;}}

else {cout <<"i="<<i<<endl;}}}

3.void silly(int n,int m)

{ if (n<1)

{ return ;}

if (n<m)

{ silly(n/2,m+1); }

else

{ silly (n/2, m); }}

4.for (int i=0;i<3*n;i++)

{

sum++;

}

for (int i=1;i<ni*=2)

{ for (int j=0;j<n*n*n;j++)

{ sum++; }}}

5. for (int i=0;i<n;i++)

{

for (int j=0;j<std::min(10,i);j++)

{ sum++;}}

Question 2
Given the following list of values, perform a binary search for the indicated search item. Show the values of first, last and middle, and the number of comparisons made after each iteration of the loop. Your should create a table like the following to show your work, where first and last are the values of the variables at the beginning of the loop, and mid is the midpoint used during that iteration, list[mid] is the value in the list at the midpoint, and No. of key comparisons should be the number of comparisons made during this iteration by the algorithm:

Iteration first last mid list[mid] no of key comparisons

1 0 12 ? ? ?

list [7,9,9,9,10,12,19,20,22,28,28,29,29]

Searching for value:22

Answer 1

Question 1.

1. Refer to the below image for how to calculate the time complexity for the 1st part.

  

The first for loop runs for n times, while for every iteration of the first for loop, the second for loop runs (n/2) times. Thus, the total number of times that the sum++; statement runs is n*(n/2) which is O(n²).

Hence, T(n) =  O(n²).

2. Refer to the below image for how to calculate the time complexity for the 2nd part.

The first for loop runs for (n/2) times, while for every iteration of the first for loop, the second for loop runs (100*n*n) times.

Hence, T(n) = (n/2)*(100*n*n) = O(n³).

3. Refer to the below image for how to calculate the time complexity for the 3rd part.

When the value of n is 1, the first if statement will become true and hence the time complexity will be O(1). but in the worst case, the 2nd or 3rd if statement will be executed and thus, the time complexity will be O(log₂n), since n is decreasing exponentially, by powers of 2. It is clearly explained in the above figure.

4. The second for loop, i.e., for (int i=1;i<ni*=2), is not clear in this part. There is no variable called ni, and you can't assign a value to a variable inside a for loop statement. Thus, this statement is incorrect.

5. This part is a little tricky. Read carefully to understand better.

The std::min(a,b) function returns the minimum of the two values a and b. For example, std::min(8, 3) will return 3.

This means that std::min(10, i) will return whichever is minimum between 10 and i.

Thus, when i<10, std::min(10, i) will always return i. When i>=10, std::min(10, i) will return 10.

This means that for i=1, the nested "for" loop will run for 1 time, for i=2, it will run for 2 times, for i=3, it will run for 3 times, and so on till i=10. Thus, for i = 0 to 9, the nested loop will run for (1+2+3+...+9) times.

When i>=10, the nested loop will always run for 10 times, independent of the value of i. Thus, for i=10 to (n-1), the nested for loop will run for ((n-10)*10) times.

Thus, the total time complexity will be:

T(n) = (1+2+3+...+9) + ((n-10)*10)

= 45 + 10*n - 100

= O(n)

Hope, you have understood how to calculate the time complexities for the given code snippets. If it helped, please consider giving positive ratings :)