Analyze the following code fragments and write down the Big-O estimates of the following code fragments. Provide a concise explanation how you got your answer.
c. for (int j = 0; j < n; j++)
{
for (int k = 0; k < n; k++)
cout << (j + k) << endl;
}
d. while (n > 1)
{
k += n *3;
n = n / 2;
}
e. int temp = n;
for (int j = 0; j < n; j++)
{
while (temp > 1)
temp = temp / 2;
}
c.
for (int j = 0; j < n; j++)
{
for (int k = 0; k < n; k++;
cout << (j + k) << endl;
}
Answer: O(n2)
Explanation:
1. The given method has nested for loop.
2. The inner loop executes n times and the outer loop also executes n times, Hence the total complexity isO(n2).
d.
while (n > 1)
{
k += n *3;
n = n / 2;
}
Answer: O(n/2)
Explanation:
Complexity is considered to be the worst case implementation, Let us consider the n = 2; Then the while loop is executed 1 time;
Let the n value is 8; then the loop is executed 3 times; As the value of n increses the number times the loop execution decreases, but when compared to the worst case scenario, the maximum times the statements executed is n/2;
So the complexity is O(n/2).
e.
int temp = n;
for (int j = 0; j < n; j++)
{
while (temp > 1)
temp = temp / 2;
}
Answer: O(n)
Explanation:
The inner executes n/2 as explained in the part e. similarly the outer loop executes n times. So the complexity is O(n, n/2). The maximum of two is n. Therefore the complexity is O(n).
Analyze the following code fragments and write down the Big-O estimates of the following code fragments....
Analyze the following code fragments and write down the Big-O estimates of the following code fragments. Provide a concise explanation how you got your answer. c. for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) cout << (j + k) << endl; } d. while (n > 1) { k += n *3; n = n / 2; } e. int temp = n; for (int j...
(10') 6. For each of the following code blocks, write the best (tightest) big-o time complexity i) for (int i = 0; ǐ < n/2; i++) for (int j -0: ni j++) count++ i) for (int í = 0; i < n; i++) for (int ni j0 - for (int k j k ni kt+) count++ İİİ) for (int í ー 0; i < n; i++) for(int j = n; j > 0; j--) for (int k = 0; k...
Show how to get the big-Oh for the following code: void CountSort (int A[N], int range) { // assume 0 <= A[i] < range for any element A[i] int *pi = new int[range]; for ( int i = 0; i < N; i++ ) pi[A[i]]++; for ( int j = 0; j < range; j++ ) for ( int k = 1; k <= pi[j]; k++ ) cout << j << endl; }
What is the output from each of the following segments of C++ code? Record the output after the “Answer” prompt at the end of each program fragment. Assume all variables have been suitably declared. (Each problem is worth 3 points.) 1. for (int j = 25; j > 16; j -= 3) cout << setw(5) << j; Answer: 2. int sum = 0; for (int k = -2; k <= 2; k++) sum = sum +...
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 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 } }
I need help fixing my code: In C++ *************** 1) I want to sum the digits of an n*n matrix 2) find the average I have completed the rest ****Do not use C++ standard library. You must use pointers and pointer arithmetic to represent the matrix and to navigate through it. MY CODE: (I have indicated at which point I need help) #include <iostream> using namespace std; void swap(int *xp, int *yp) { int temp = *xp; *xp = *yp;...
c++ Please give a line by line explanation fo the design of this code (what is happening per line to make this program work) int ways(int amt,int* l,int n,int* res){ if (amt < 0 || (amt > 0 && n <= 0)) return 0; if (amt == 0){ string s = ""; int j = 0; if (res[0] > 0){ j = 1; cout << res[0] << " quarter/s, "; } if (res[1] > 0) { j = 1; cout...
points): Show the output of the code below as it would appear on the monitor. int main cout <<" <<endl: int wildcat 2: while (wildcat > 5) cout << wildcat <<endl; wildcat++ cout <K*<< endl; int jayhavk 5i do cout << jayhawk <s endl: while (jayhawk0) cout <<*" << endl; int wolverine l: while (wolverine 0 &&wolverine < 10) cout << wolverine <<endl: wolverine2: cout <<" <<endl: for (int zag-4; zag>0; zag_) cout <<****" << endl; for (int i-10; i<-30;...
For each of the below code snippets, identify the bounding function (the big O) of the number of times the indicated line is run (justify your answer briefly): int i = 1: while (i < n) { printf ("Insert difficult work here!") i = i + i: } for(i = 0: i < n: i++) { for (j = 0: j < n: j++) { for (k = 0: k < n: k++) { if(i==j && j==k) arr[i] [j] [k]...