Question

What is the time complexity of the following code? (in big-O notaion) sum = 0 count...

What is the time complexity of the following code? (in big-O notaion)
sum = 0

count = 0

var1 = 0

for: i=1 to n{

sum = sum+i

for j=1 to [(3i+2i)(5n)(2i)]{

var1 = sum+count}

}

for m = i to j*j{

sum = sum*sum

var2 = sum - (count+3)}

Homework Answers

Answer #1

As we know that big O notation is a fundamental tool to compute the complexity in mathematical term.

so formula would be f(x)<= cg(x) where c is constant , it could be any constant. for example

f(x)= 2x2 +3x + 5 <= 20x2 +33x + 5

                               <= 20x3 +any thing

                               <= 20x4 +33x + anything all would be BigO notation

so now i am comming to the point of question, i have devide whole code in line so that during the interpretation it would be easy to understand.

see the carefully code line 4 it would be go 1 to n , if here i take n=5 the 1 to 5 so line 5 will take constant time when we talk about the big number for n then it would be negligible, now calculate theline 6 and line 9 to 11, normally if we understand of line 6 see

Here third loop is independent , and i and j is defined local variable, if we assume to both varibale independent, so m=i go j*j if j = n then it will go n2 so so now we can write as assemble the whole thing :

c(constant)+n3 + n2 +c(constant) =O(c*n3)

i hope you got the main thing

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Show that the running time for the following segment of code is O(N3) without using the...
Show that the running time for the following segment of code is O(N3) without using the rule for loop. Make sure to count each statement that takes one unit of time. sum = 0; for( i = 0; i < n; i++ ) for( j = 0; j < n; j++ )             for( k = 0; k < n; k++ ) sum++;
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm...
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm that is executed most frequently. Express the number of times it is executed as a function of N. Convert this expression into the Big-O notation. A. For each of the three fragments of code, what is its worst-case time complexity, in the form "O(…)". (Use the given solution to the first problem as a model)                 //----------------- This is a sample problem – solved ------...
2. Write the big-O expression to describe the number of operations required for the following two...
2. Write the big-O expression to describe the number of operations required for the following two pieces of code. You need to explain your solution and show your work. (3 points) code 1: counter = 0       for (i = 1; i < n; ++i) {           for (j = 1; j < i; j++) { counter++; }    } code 2: counter = 0; for (i = 1; i < n; ++i) { for (j = 1; j <...
Given the recursive bubble sort algorithm, analyze its time complexity in terms of Big O. bubbleSort(A[],...
Given the recursive bubble sort algorithm, analyze its time complexity in terms of Big O. bubbleSort(A[], n) { // Base case if (n == 1) return;    // One pass of bubble sort. After // this pass, the largest element // is moved (or bubbled) to end. for (i=0; i<n-1; i++) if (A[i] > A[i+1]) swap(A[i], A[i+1]);    // Largest element is fixed, // recur for remaining array bubbleSort(A, n-1); }
Analyze the worst case running time of the following code in “big-Oh” notation in terms of...
Analyze the worst case running time of the following code in “big-Oh” notation in terms of the variable n. a. void fdisp1(int n) { for(int i=0; i < n; i++) { for(int j=0; j < n; j++) { for(int k=0; k < n; k++) { for(int m=0; m < n; m++) { System.out.println("Hi I am Here"); } } } } } b. voidprintAllPossibleOrderedPairs(intarr[], int size) { for (int i = 0; i < size; i++) { for (int j =...
Use Big-O Notation to characterize the computational cost of algorithm A1 and A2. The complexity of...
Use Big-O Notation to characterize the computational cost of algorithm A1 and A2. The complexity of A1 is 10000 * n, with n being the number elements processed in A1. The complexity of A2 is 100 * n, with n elements in A2. State in Big-O notation the cost of f1, with f1(x) = log2(2x) – 14x + 3 sqrt(x) + 12x^2 - 150 this is also a theoretical question just answer no code.
As a function of n , what is the flop count of the following code, s=0...
As a function of n , what is the flop count of the following code, s=0 for k=1:n , s=s-j-1 for j=k:n , s=s+k+j^2*(k-1) end end
Find the big-O, big-Omega of the following functions (show steps please) a) f(n) = 5n^2 +...
Find the big-O, big-Omega of the following functions (show steps please) a) f(n) = 5n^2 + 1 b) f(n)= (nlogn+1)*(n+1)
Question 4.5 Consider the fragment in Algorithm 4.8 shown below. Algorithm 4.8 sum = 0; for...
Question 4.5 Consider the fragment in Algorithm 4.8 shown below. Algorithm 4.8 sum = 0; for (i =1; i <=f(n); i ++) sum += i; Here f(n) is a function call. Give a simple and tight Big-Oh upper bound on the running time of Algorithm 4.8, as a function of n, on the assumption that (a) the running time of f(n) is O(n), and the value of f(n) is n!. (b) the running time of f(n) is O(n), and the...
   1)T(n) = 27 T (n/3) + n3 2)Calculate the running time for the following code...
   1)T(n) = 27 T (n/3) + n3 2)Calculate the running time for the following code fragment. Algorithm test int counter, i, j; counter := 0; for (i:= 1; i < n; i*=2) { for (j:= 0; j < i; j++) { counter := counter +1 } } 3)Let f(n) = 2lg 8n + 3 be a function.