please i need answer for b cd e and f For each of the code s

please i need answer for b, c,d, e and f.

For each of the code segments below, determine an equation for the worst-ease computing time T(n) (expressed as a function of n. i.e 2n + 4) and the order of magnitude (expressed using big O notation, i.e. O(n)). b.//Matrix addition for (int i = 0; i

Solution

Ans.

b. Matrix Adddition :

First for loop executes n no of times and inner for loop executes n no of times.

Therefore, T(n)= n² + c where c is a positive constant required to execute the assignment operation inside nested for loop.

O(n)=n²

(In the worst case, both for loops would run for n no of times, and since O() represents the worst case scenario, hence the highest order of T(n) is taken into consideration, please keep this in mind for the next subproblems as well)

c. Matrix Multiplication :

Since the first assignment operation, i.e, c[i][j] = 0, takes place for n² no. of times and the second assigment operation c[i][j] += a[i][k] * b[k][j] , takes place n³ no of times, hence we can deduce:

T(n) = n³ + n² + c

Since O(n) takes the highest magnitude of T(n) (since its the worst case scenario)

O(n) = n³

d. Bubble Sort :

Here outer for loop executes (n-1) times and inner loop also executes (n-1) times.

At worst case the if condition gets executed (n-1)*(n-1) times and if we assume that the swapping of vairables take linear time then the assignment operations can be expressed in terms of some constants say c.

Thus T(n) = (n-1)² + c     =>   n² -2n+1+c    => n²-2n+c

O(n) = n² (Taking highest magnitude of T(n)).

e. In worst case if we assume n is very large then for each execution of while loop value of n is getting halved.

For 1st iteration : n/2

For 2nd iteration: n/2²

For kth iteration : n/2^k

Thus : T(n) = n/2^k + c

Now, let n/2^k = i

Applying log on both sides , log(n/2^k) = log(i)

                                       => log(n) - log(2^k) = log(i)

                                       => log(n) - k = log(i)

   => k = log(n) - log(i) => k = log(n) + c , since log(i) is a constant

Hence we can deduce, O(n) = log(n).

f. Since the first for loop exectes for (n-1) times and the second for loop can be explained as below:

1st iteration : 1

2nd iteration: 2

3rd iteration: 4

nth iteration: 2ⁿ

Hence, T(n) = (n-1)*2ⁿ + c => T(n) = n2ⁿ - 2ⁿ + c => T(n) = nlog(n) - log(n) + c

Now considering highest magnitude for worst case scenario O(n)

O(n) = nlog(n)