Question

1. (25 points) Assume each expression listed below represents the execution time of a program Express the order of magnitude for cach time using big O notation. a. T(n) = ns + 100n . log2 n + 5000 b. T(n) = 2" +n” + 7 d. T(n) 1+2+4+2 2 (75 points+5 extra credit) For cach of the code segments below, determine an equation for the worst-case computing time Tn) (expressed as a function of n, ie. 2n+4) and the order of magnitude (expressed using big O notation, ie. O(n) a. 1/ Calculate nean sum “ 0; cin >> x; while (x --999) sum+X cin > nean-sum/n 2. (continued) (75 points) For each of the code segments below, determine an equation for the ie, 2n + 4) nd the order of worsl-case computing time TR, (expressed as a functon of magnitude (espressed using big O notation, Le. Om b. I/ Matrix addition for (int i-0; i < n; i++) { for (int j " 0; j < n; j++) { I/ Hatrix maltiplication for (int j-0, j < n, j++) { for (int k-0: k<ni k+) d. // Bubble sort for (int i-Ozǐくn-1;i++) { for (int 1 131-xts 15+11-temp while (n ni-2 e, >-1) f. (extra credir-5 points for (int-1: Cn-: 1) for lint- cout ce < endl: x2

Answer 1

ANSWER::-

AS FOR GIVEN DATA....

Points considered while calculating Big O notation , we drop constants like O(5N) will become O(N), also we drop additions or subtractions , O(N-2) becomes O(N).

a) T(n) = n3 + 100 N.log2n + 5000

We will drop constants

n3 + log2n
O(n3) + O(log(n))

b) T(n) = 2n + n99 + 7

Here 2^n will varry according to n hence the time taken for n^99 will define the time complexity for 2^n as well so we drop it and 7 is constant so we will drop that as well

Hence it will be O(n^99)

c) T(n) = n^2-1/n+1 + 8log2n

Here n^2-1 will be treated as (n^2) and n+1 will be as O(n) hence O(n) will be covered by O(n^2) so it becomes O(n^2) and 8log2n will be O(log(n)

So, O(n^2) + O(log(n))

D) T(n) = 1+2+....+2n-1

the expression completely depends on 2^n-1 so O(n-1)

2. Since the loop doe not depend on value of n instead it depends on value of x , which has to be entered by user.if user never enter x -999 then loop will be executed infinitly in the worse case, big o

O(∞)

best case O(1) when user enter x !=999 , and once in while loop enters -999 , so loop executed for one time