Please note that A, B, and C are the questions that need to be answered for each
ID: 3591630 • Letter: P
Question
Please note that A, B, and C are the questions that need to be answered for each loop below. A should Derive a formula, f(N) to count the number of indicated operations as a function of N in each of the following code segments. B should Determine a tilde approximation for f(N). C should Determine the order of growth for each of the following code segments. There are placeholders for A, B, and C and the end of each loop question. These are to be filled in with the answers.
Thanks!
1. for (int i = 1; i <= N; i++) --> comparisons
for (int j = 1; j <= N; j++ )
if ( a[i] < a[j]) ) c++;
A.
B.
C.
2. for (int i = 2; i <= N; i += 4) --> comparisons
for (int j = 1; j <= N; j += 3 )
if ( a[i] < a[j]) ) c++;
A.
B.
C.
3. for (int i = 0; i < N; i++) --> comparisons
for (int j = i+1; j <= N; j++ )
if ( a[i] < a[j]) ) c++;
A.
B.
C.
4. for (int i = 0; i < N; i++) --> multiplys
for (int j = 0; j < N; j++ )
for (int k = 0; k < N; k+=2)
a[k] = a[i] * a[j];
A.
B.
C.
You can assume N= 2n if it helps
5. for (int i = 1; i multiplys
a[i] = a[i-1] * 2;
A.
B.
C.
Explanation / Answer
1. for (int i = 1; i <= N; i++) --> comparisons
for (int j = 1; j <= N; j++ )
if ( a[i] < a[j]) ) c++;
A. (n^2+1) comparisons (since two for loops n*n)
B. n^2
C. O(n^2)
--------------------------------------------------------------------------------------------------------------------------------------------------------
2. for (int i = 2; i <= N; i += 4) --> comparisons
for (int j = 1; j <= N; j += 3 )
if ( a[i] < a[j]) ) c++;
A. (n-4)*(n-3) comparisons, but mostly denoted as n comparisons
B. n^2
C. O(n^2)
----------------------------------------------------------------------------------------------------------------------------------------------------
3. for (int i = 0; i < N; i++) --> comparisons
for (int j = i+1; j <= N; j++ )
if ( a[i] < a[j]) ) c++;
A. n*(n-1) comparisons
B. n^2
C. O(n^2)
-------------------------------------------------------------------------------------------------------------------------------------------------------
4. for (int i = 0; i < N; i++) --> multiplys
for (int j = 0; j < N; j++ )
for (int k = 0; k < N; k+=2)
a[k] = a[i] * a[j];
A. (n^3 + 1) multiplys
B. n^3
C. O(n^3)
-----------------------------------------------------------------------------------------------------------------------------------------------------
You can assume N= 2n if it helps
5. for (int i = 1; i multiplys
a[i] = a[i-1] * 2;
A. 4n^2 multiplys
B. 2n^2
C. n^2
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.