What are the amortized worst-case complexities of the methods g and h? What is the amortized...

     

Transcribed Image Text:

• What are the amortized worst-case complexities of the methods g and h? What is the amortized average complexity of p? Motivate • Complete the following table where k is a constant. The bounds should be as tight as possible. Leave the cell empty, if you think the corresponding bound does not exist. Function 1= n log log nnlog nk + n² kn¹/2 n is even 2= nis odd 3= n logn 3√nk-nk O Ω e int g(int n) { int sum=0; for (int i=0; i<n; ++i) sum + 1/2; for (int i=0; i<n; ++i) for (int ji; j<n; ++j) for (int k-j; k<n; ++k) sum +i+j+k; return sum; } int p(int n) { int k-random (0,n); for (int i=0; i<n + k; ++i) sum++=i; if (k == n) { for (int i=0; i<n; ++i) sum += p (i); } return sum; int h(int n, int k) { int k = 0; while (k <1000) { } for (int i=0; i<n; ++i) for (int ji; j<n; j-j*2) print (j); k++; • What are the amortized worst-case complexities of the methods g and h? What is the amortized average complexity of p? Motivate • Complete the following table where k is a constant. The bounds should be as tight as possible. Leave the cell empty, if you think the corresponding bound does not exist. Function 1= n log log nnlog nk + n² kn¹/2 n is even 2= nis odd 3= n logn 3√nk-nk O Ω e int g(int n) { int sum=0; for (int i=0; i<n; ++i) sum + 1/2; for (int i=0; i<n; ++i) for (int ji; j<n; ++j) for (int k-j; k<n; ++k) sum +i+j+k; return sum; } int p(int n) { int k-random (0,n); for (int i=0; i<n + k; ++i) sum++=i; if (k == n) { for (int i=0; i<n; ++i) sum += p (i); } return sum; int h(int n, int k) { int k = 0; while (k <1000) { } for (int i=0; i<n; ++i) for (int ji; j<n; j-j*2) print (j); k++;

Answer rating: 100% (QA)

To address the first part of the question lets analyze the methods g h and p to determine their complexities starting with g and h Amortized WorstCase Complexity of g The method g has three nested loo... View the full answer