Question

What is the time-complexity of the following code? Explain, please. for(i = 1; i < 3n;...

What is the time-complexity of the following code? Explain, please.

for(i = 1; i < 3n; i++){

for(j=1; j < 2n; j++){

for(k=1; k < n; k*=2){

m += j;

}

}

}

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1 
for(i = 1; i < 3^n; i++)
Values of i in this loop are 1,2,3,4,....,
So, Number of values for i = 

for(j=1; j < 2^n; j++)
Values of j in this loop are 1,2,3,4,....,
So, Number of values for j = 

for(k=1; k < n; k*=2)
Values of i in this loop are 1,2,4,8,....,n
So, Number of values for k = log(n)

Time complexity = O( log(n))

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
What is the tilde time complexity for the following code fragments: 1) int sum = 0;...
What is the tilde time complexity for the following code fragments: 1) int sum = 0; for (i = n; i > 0; i /= 2) for (j = 0; j < i; j++) sum++; 2) int sum = 0; for (int i = 0; i < n; i++) for (int j = 0; j < i; j+=2) sum++;
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)}
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 ------...
What is the time complexity of the following segment of code assuming that the function temp...
What is the time complexity of the following segment of code assuming that the function temp takes time O(n)? ... ... x = n y = n while y > 1:      print(x)      temp(x)      y = y / 2      x = x – 1 temp(x) … …
1.) the following code fragments give running time analysis (Big Oh). Explain your answer: sum2 =...
1.) the following code fragments give running time analysis (Big Oh). Explain your answer: sum2 = 0; sum5 = 0; for(i=1; i<=n/2; i++) { sum2 = sum + 2; } for(j=1; j<=n*n; j++) { sum5 = sum + 5; } i think it is O(n^2) since big oh finds the order of worst case which is the the second loop being n^2 complexity. but im not sure. 2.) Give an efficient algorithm along with running time analysis to find the...
find time complexity in terms of n? use big-O i,j,k,x =0; for i=0; i<=n; i++; for...
find time complexity in terms of n? use big-O i,j,k,x =0; for i=0; i<=n; i++; for j=0, j<=5; j++; for k=5; k<=n; k=k*5; x = x*n;
Analyze the following code and provide a "Big-O" estimate of its running time in terms of...
Analyze the following code and provide a "Big-O" estimate of its running time in terms of n. Explain your analysis. for ( int i = n; i > 0; i /= 2 ) { for ( int j = 1; j < n; j += 2 ) { for ( int k = 0; k < n; k += 2 ) { ... // constant number of operations } } }
Please provide a mathematical analysis for the following code: for (i=0; i < n-1; i++) for...
Please provide a mathematical analysis for the following code: for (i=0; i < n-1; i++) for (j=i+1; j < n; j++) { tmp = A[i][j]; A[i][j] = A[j][i]; A[j][i] = tmp; }
Answer the following questions: 1. Given the code segments below with n as the problem size,...
Answer the following questions: 1. Given the code segments below with n as the problem size, answer the following questions: //Code Segment 1 (Consider n as a power of 3) int sum = 0; for(int i = 1; i <= n; i = i*3) sum++;​​​​​​​// statement1 //Code Segment 2: (Consider both possibilities for x) if(x < 5){ for(int i = 1; i <= n; i++)    for(int k = 1; k <= i; k++)    sum++;​​​​​// statement2 } else{ for(int...
(Java) For the following code segment, match the different values of the empty line with the...
(Java) For the following code segment, match the different values of the empty line with the resulting Big O complexity of the algorithm. int n = int k = 0; for (int i=0; i <= n; i++){ int j = i; while (j > 0) { // ___MISSING CODE___ k++; } } j = 0; j--; j /= 2; j = j * 2; Options for each are: O(n^3)            O(n * log n)            an...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT