What is the Θ( ) for each code segment below? (a) for( int i = 1,...

What is the Θ( ) for each code segment below?

(a) for( int i = 1, i<= n, i = i*2){

some constant operation

}

(b) for( int i = 1, i<= n, i++){

for( int j = 2*i, j<=n, j++){

some constant operation

}

for( int j = 1, j<=n, j = j*2){

some constant operation

}

Solutions

Expert Solution

This code has one loops

Values of i during first loop are from 1,2,4,8,..,n
So, First loop running for log(n) times

Time complexity
= O(Number of times loop runs)
= O(log(n))

===========================================

This code has two loops

Values of i during first loop are from 1,2,3,..,n
So, First loop running for n times

Values of j during first loop are from 2*i,2*i+1,,..,n
So, Second loop running for n-2i times
So, in worst case second loop running for n times

Time complexity
= O(Product of number of times both loop runs)
= O(n*n)
= O(n^2)

===========================================

This code has two loops

Values of i during first loop are from 1,2,4,8,..,n
So, First loop running for log(n) times

Values of j during first loop are from 1,2,4,8,..,n
So, Second loop running for log(n) times

Time complexity
= O(Product of number of times both loop runs)
= O(log(n)*log(n))
= O(log(n)^2)

venereology answered 3 months ago

Next > < Previous

Related Solutions

What is the ouput of the following code? void loop(int num) { for(int i = 1;...

What is the ouput of the following code? void loop(int num) { for(int i = 1; i < num; ++i) { for(int j = 0; j < 5; ++j) { cout << j; } } } int main() { loop(3); return 0; }

C++ Q2. Given the code as below. Which statement is correct? int myAry[100]; for(int i=0; i<100;...

C++ Q2. Given the code as below. Which statement is correct? int myAry[100]; for(int i=0; i<100; i++) myAry = i + 2; for(int i=100; i>0; i--) cout << myAry[i] << '\t'; The first for loop assigns myAry 99 values and the null character. The second for loop prints out myAry elements backwards. The index in the second for loop is out of bounds. Only the first loop needs the null character. Q3. A value returning function that takes one parameter,...

1)What is the output of the following code? struct someType { int a; int b; };...

1)What is the output of the following code? struct someType { int a; int b; }; void f1(someType &s) { s.a = 1; s.b = 2; } someType f2(someType s) { someType t; t = s; s.a = 3; return t; } int main() { someType s1, s2; f1(s1); s2 = f2(s1); cout << s1.a << '-' << s1.b << '-' << s2.a << '-' << s2.b << '-' << endl; return 0; } ------------------------------------------------------------------------------------------------------------------ 2) struct dateType { int...

Question 31 Given the code snippet below, what prints? void fun(int *p) { int q =...

Question 31 Given the code snippet below, what prints? void fun(int *p) { int q = 10; p = &q; } int main() { int r = 20; int *p = &r; fun(p); cout << *p; return 0; } Question 31 options: 10 20 compiler error Runtime error Question 32 A union’s members are exactly like the members of a Structure. Question 32 options: True False Question 33 Given the code below, what are the errors. #include <iostream> using namespace...

1. Convert the following code shown below to C++ code: public class HighwayBillboard { public int...

1. Convert the following code shown below to C++ code: public class HighwayBillboard { public int maxRevenue(int[] billboard, int[] revenue, int distance, int milesRes) { int[] MR = new int[distance + 1]; //Next billboard which can be used will start from index 0 in billboard[] int nextBillBoard = 0; //example if milesRes = 5 miles then any 2 bill boards has to be more than //5 miles away so actually we can put at 6th mile so we can add...

For a fixed θ>0, let X1,X2,…,Xn be i.i.d., each with the beta (1,θ) density. i) Find...

For a fixed θ>0, let X1,X2,…,Xn be i.i.d., each with the beta (1,θ) density. i) Find θ^ that is the maximum likelihood estimate of θ. ii) Let X have the beta (1,θ) density. Find the density of −log⁡(1−X). Recognize this as one of the famous ones and provide its name and parameters. iii) Find f that is the density of the MLE θ^ in part (i).

1. What will be the value of numbers[1] after the following code is executed? int[] numbers...

1. What will be the value of numbers[1] after the following code is executed? int[] numbers = {22, 33, 44}; for(int k = 0; k < 3; k++) { numbers[k] = numbers[k] + 5; } } 2. What will be the results of the following code? final int ARRAY_SIZE = 5; double[] x = new double[ARRAY_SIZE]; for(int i = 1; i <= ARRAY_SIZE; i++) { x[i] = 10.0; } 3.What is the value of numbers [3] after the following line...

Please explain this code line by line void printperm(int *A,int n,int rem,int j) { if(n==1)...

Please explain this code line by line void printperm(int *A,int n,int rem,int j) { if(n==1) { for(int k=0;k<j;k++) cout<<A[k]<<" + "; cout<<rem<<"\n"; return; } for(int i=0;i<=rem;i++) { if(i<=rem) A[j]=i; printperm(A,n-1,rem-i,j+1); } }

Trace the following code segment 1. use the red numbers under each statement to show the...

Trace the following code segment 1. use the red numbers under each statement to show the order that you execute the code by. For example: (1) means int p=3; (2) means p<10; (3) means p+=3; (1)(2)(3) means you execute int p=3 then p<10 then P+=3; (2)(1)(3) means you execute p<10 then int p =3 then P+=3; 2. show its output for (int p = 3 ; p <10; p += 3 ) (1) (2) (3) { for...

Trace the following code segment 1. use the red numbers under each statement to show the...

Trace the following code segment 1. use the red numbers under each statement to show the order that you execute the code by. For example: (1) means int p=3; (2) means p<10; (3) means p+=3; (1)(2)(3) means you execute int p=3 then p<10 then P+=3; (2)(1)(3) means you execute p<10 then int p =3 then P+=3; 2. show its output: int x = 30, num = 100; (1) while ( x > 0) (2) { cout << endl << “ x...

Subjects