For the following program fragment, (1) give an analysis of the running time T(n) as a...

For the following program fragment, (1) give an analysis of the running time T(n) as a function of n and (2) give a big-O bound on the asymptotic running time (tight bounds for full credit).

Sum = 0;

for (i=0; i< n; i++)

for(j=0; j < i*i; j++)

if(j % i == 0)

for (k=0; k<j; k++)

Sum = Sum + 1;

Expert Solution

Please follow the below answer.

venereology answered 9 months ago

For each of the following six program fragments give an analysis of the running time (Big-Oh...

For each of the following six program fragments give an analysis of the running time (Big-Oh will do). (25,very 5 mark) (a)sum = 0; for( i=0; i<n; i++ ) for( j=0; j<n; j++ ) sum++; (b) sum = 0; for( i=0; i<n; i++ ) for( j=0; j<n*n; j++ ) sum++; (c) sum = 0; for( i=0; i<n; i++ ) for( j=0; j<i; j++ ) sum++; (d) sum =0; for( i=1; i<n; i++ ) for( j=1; j<i*i; j++ ) if( j%1...

Analyze the following codes by computing their running time, T(n). 1) int function ( int n)...

Analyze the following codes by computing their running time, T(n). 1) int function ( int n) { int sum; for (int i = 0; i < n; i++) sum = sum + (i * n); return sum; } 2) int function(int n) { int sum; for (int i = 0; i < n; i++) if (n < 1000) sum++; else sum += function(n); } 3) int function(n) { int s = 0; for (int i = 1; i...

a) Let T(n) be a running time function defined as T(n) = 3n^2 + 2n +...

a) Let T(n) be a running time function defined as T(n) = 3n^2 + 2n + 5, is this ϴ(n^2 )? Explain prove your answer using the definitions of big-o and omega notations. b) Solve the following recurrence relations using Master theorem. a. ?(?) = 3? ( ?/3 ) + ? b. ?(?) = 5?( ?/2 ) + 2?^2 please help them with both

Question 14: Find the running time function, T(n), of the program below. def prob14(L): if len(L)...

Question 14: Find the running time function, T(n), of the program below. def prob14(L): if len(L) <= 1: return 0 output = 0 for x in L: for y in L: output += x*y for x in L: output += x left = L[ 0 : len(L)//2 ] right = L[ len(L)//2 : len(L) ] return output + prob15(left) + prob15(right) ANSWER: T(n) = ... ***Big-O, Omega, Theta complexity of functions, Running time equations of iterative functions & recursive...

Problem 10 Write down the running time function, T(n), of the program below. def prob10(L): s...

Problem 10 Write down the running time function, T(n), of the program below. def prob10(L): s = 0 for x in L: for y in L: if x+y % 10 == 0: print(x, y, x+y) s = s + x*y return s ANSWER: T(n) = ... ***Big-O, Omega, Theta complexity of functions, Running time equations of iterative functions & recursive functions, Substitution method & Master theorem Please answer within these topics.***

Give upper and lower bounds for T(n) in the following recurrence: T(n) = 3T(n/4) + n

Construct an assembly language program fragment equivalent to the following C/C++ statement: if (M <= N...

Construct an assembly language program fragment equivalent to the following C/C++ statement: if (M <= N + 3 && (C == ‘N’ || C == ‘n’)) C = ‘0’; else C = ‘1’; Assume that M and N are 32-bit signed integer variables, and C is an 8-bit ASCII character variable. All variables are stored in memory, and all general-purpose registers are available for use.

Question

For the following program fragment, (1) give an analysis of the running time T(n) as a...

Solutions

Expert Solution

Related Solutions