Calculate the running time for the following code fragment. Show your work. for (i:= 0; i...

Question

Question

Calculate the running time for the following code fragment. Show your work.

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

{

for (j:=1; j < n; j*=2)

{

counter := counter +1

}

Answer 1

Answer #1

Generally one loop nested in another will have O(n²).

in this cae j=j*2 is the pattern for j for firs for loop wil have to expcute n time where as inner for loop will be executed half than n as j =j*2.

So i will be (n*n)/2

Time complexity will be O(n^2/2) .

Let me know if you have doubts.

Answer 2

Similar Homework Help Questions

Q-1: Given the following code fragment, what is its Big-O running time? test = 0 for...

Q-1: Given the following code fragment, what is its Big-O running time? test = 0 for i in range(n): for j in range(n): test= test + i *j Q-2: Given3 the following code fragment what is its Big-O running time? for i in range(n): test=test+1 for j in range(n): test= test - 2 Q-3: Given the following code fragment what is its Big-O running time? i = n while i > 0: k=2+2 i...
c++ What is the worst-case complexity of the following code fragment: for(i = 0; i <...

c++ What is the worst-case complexity of the following code fragment: for(i = 0; i < N; i++) { for(j = 0; j < N; j++) { sequence of constant time statements } } for(i = N; i > 0; i--) { sequence of constant time statements }
1. Give the running time of the following procedures, using -notation. Show your work. procedure P....

1. Give the running time of the following procedures, using -notation. Show your work. procedure P. (n) S=0; for i n to 2n do for j = 5i to 5i+12 do ses+i-j. procedure ps(n) 560; for i« 5n to 6n do for 15 to i do for k j to i do ses+i-j. procedure pe(n) S=0; for i1 to 5n do begin j4i ; while j<i' do begin 5 5 +i-j; je 5; end end

Exercises • Determine running time for the following code fragments: (a) a = b + c;...

Exercises • Determine running time for the following code fragments: (a) a = b + c; d = a + e; (b) sum = 0; for (i=0; i<3; i++) for (j=0; j<n; j++) sum++; (c) sum=0; for (i=0; i<n<n; i++) sum++; (d) 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; (e) sum = 0; for (i=1; i<=n; i++) for (j=1; j<=n; j+=2) sum++;
Show your work Count the number of operations and the big-O time complexity in the worst-case...

Show your work Count the number of operations and the big-O time complexity in the worst-case and best-case for the following code int small for ( i n t i = 0 ; i < n ; i ++) { i f ( a [ i ] < a [ 0 ] ) { small = a [ i ] ; } } Show Work Calculate the Big-O time complexity for the following code and explain your answer by showing...
In Big-Θ notation, analyze the running time of the following pieces of code/pseudo-code. Describe the running...

In Big-Θ notation, analyze the running time of the following pieces of code/pseudo-code. Describe the running time as a function of the input size (here, n) for(int i=n-1; i >=0; i--){ for(int k=0; k < i*n; k++){ // do something that takes O(1) time } }

What is the Big-Oh order of the following code fragment? The fragment is parametrized on the...

What is the Big-Oh order of the following code fragment? The fragment is parametrized on the variable N. Assume that you are measuring the number of times j is decremented. public static void sort(Comparable[] a) { int N-a.length; for (int i = 1; i < N;i++) { for (int j = i; j > && less(a[5], a[j-1]); j--) //measure j -- exch(a, j, j-1); O(nlogn) O O(n^2) Q(n) Does not exist.
Compute the total running time for each of the functions in the following code. First, compute...

Compute the total running time for each of the functions in the following code. First, compute the running time in terms of some constants a, b, c, d, e, etc. Show your work and give the answer in the text box. Then give the tightest big-O bound you can for each. (All of the functions are O(n!), but you can give a more informative bound for each.) void f(int n) { int i = 1; while (i <= sqrt(n)) {...
Using MIPS: Consider the following fragment of C code: for i=0: i < = 100: i...

Using MIPS: Consider the following fragment of C code: for i=0: i < = 100: i = i + 1) {a[i] = b[i] + c;} Assume that a and bare arrays of words and the base address of a is in $a0 and the base address of b is in $a1. Register $t0 is associated with variable i and register $s0 with c. Write the code for MIPS. How many instructions are executed during the running of this code? How...

Question 1 (25 pts) Find the running time complexity for the following code fragments. Express yo...

Question 1 (25 pts) Find the running time complexity for the following code fragments. Express your answers using either the Big-O or Big-Θ notations, and the tightest bound possible. Justify your answers. for(int count O , i -0; i < n* n; i++) for(int i0 ; j <i; j++) count++ for(int count O , i -0; i