Show how to get the big-Oh for the following code: void CountSort (int A[N], int range)...
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;
}
Homework Answers
`Hey,
Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.
Since there are 2 loops but, they are not nested. So, first for loop has complexity of
O(n)
Second for loop will have complexity of O(N+range)
So,
total complexity is O(N+range)
Kindly revert for any queries
Thanks.
Add Answer to:
Show how to get the big-Oh for the following code:
void CountSort (int A[N], int range)...
Problem 1. Select the running time of each function. void print_array (int* A, int n) for...
Problem 1. Select the running time of each function. void print_array (int* A, int n) for (int í 0; i < n; ++i) cout << A[i] << endl; void print_array pairs (int* A, int n) for (inti 0; i < n; ++i) for (int j 0; j < n; ++j) cout << Ai] ALj]< endl; void print_array_start(int* A, int n) for (int i 0; i < 100 ; ++i) cout << A[i] << endl; void print_array_alt (int* A, int 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...
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...
points): Show the output of the code below as it would appear on the monitor. int...
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;...
find complexity Problem 1 Find out the computational complexity (Big-Oh notation) of the code snippet: Code...
find complexity Problem 1 Find out the computational complexity (Big-Oh notation) of the code snippet: Code 1: 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 here } } } Code 2: Hint: Lecture Note 5, Page 7-8 void f(int n) { if (n...
Explain the output of the following C++ program. #include <iostream> using namespace std; void Magic(int i=1,...
Explain the output of the following C++ program. #include <iostream> using namespace std; void Magic(int i=1, int j=2,int k=3, double product =1.0) { i+=2; j*=2; k/=2; product=i*j*k; } void Magic(int& i, int& j, double& product) { i+=2; j=j*2+2; product=i*j; } void Magic(int* i,int* j) { double product; *i+=2; *j=*j*2+2; product=*i * *j; } int main() { double product; int i=0,j=0,k=0; product=i*j*k; Magic(); cout<<"i, j, k and product in main () after 1st round:"<<endl<<i<<endl<<j<<endl<<k<<endl<<product<<endl; Magic(2,4); cout<<"i, j, k and...
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...
12. What is the output of the following C++ code? int x; int y; int *p...
12. What is the output of the following C++ code? int x; int y; int *p = &x; int *q = &y; *p = 35; *q = 98; *p = *q; cout << x << " " << y << endl; cout << *p << " " << *q << endl; 13. What is the output of the following C++ code? int x; int y; int *p = &x; int *q = &y; x = 35; y = 46; p...
Give the output for the following code assume int globalvar 10: above the function prototypes void...
Give the output for the following code assume int globalvar 10: above the function prototypes void foo(int&); void bar(int); int main() { int globalVar = 5; foo(globalVar); cout << globalVar << endl; bar(globalVar); cout << globalVar << endl; return 0; } void foo(int& x) { x = globalVar + x; cout << globalVar << endl; return; void bar(int x) { globalVar + x; cout << globalVar << endl; X = return;
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.
Problem 1. Select the running time of each function. void print_array (int* A, int n) for (int í 0; i < n; ++i) cout << A[i] << endl; void print_array pairs (int* A, int n) for (inti 0; i < n; ++i) for (int j 0; j < n; ++j) cout << Ai] ALj]< endl; void print_array_start(int* A, int n) for (int i 0; i < 100 ; ++i) cout << A[i] << endl; void print_array_alt (int* A, int n)...
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;...
Give the output for the following code assume int globalvar 10: above the function prototypes void foo(int&); void bar(int); int main() { int globalVar = 5; foo(globalVar); cout << globalVar << endl; bar(globalVar); cout << globalVar << endl; return 0; } void foo(int& x) { x = globalVar + x; cout << globalVar << endl; return; void bar(int x) { globalVar + x; cout << globalVar << endl; X = return;
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.
Most questions answered within 3 hours.
-
Assume a muscle has a PCSA = 20 cm2 and Lo = 12 cm. Assume it...
asked 1 hour ago -
What is the yield to maturity of a ten-year, $1,000 bond with a
5.2% coupon rate...
asked 1 hour ago -
A mass m = 5 kg is tied on one end of a rope and is...
asked 1 hour ago -
The Average sales price of single-family houses in Charlotte is
$210,000 with a standard deviation of...
asked 1 hour ago -
Target Costing
Laser Impressions, Inc., manufactures color laser printers.
Model J20 presently sells for $225 and...
asked 1 hour ago -
a bottle cap manufacturer with four machines and six operators
wants to see if variation in...
asked 2 hours ago -
State Farm Insurance studies show that in Colorado, 55% of the
auto insurance claims submitted for...
asked 3 hours ago -
Complete the following reactions which form ethers (A
and B) and cyclic ethers (C-E) as major...
asked 3 hours ago -
in a perfectly elastic collision what is the velocity of ball A
if the original direction...
asked 4 hours ago -
PLEASE ANSWER ALL
1) The pressure of the atmosphere decreases with increasing
altitude in the
Choose...
asked 4 hours ago -
A simple random sample of 25,000 individuals are surveyed in
order to determine the prevalence of...
asked 4 hours ago -
People who do very detailed work close up, such as jewelers,
often can see objects clearly...
asked 4 hours ago