Your post is appropriate and correct, except for one statement which is inconsistent: "The space complexity is O(n), no extra space us needed. " O(n) contradicts no extra space. Please clarify. Class, As interaction contribution, you may try to answer the following question: Q: Indeed, the complexity is Theta(n^2) . However, there is a difference in number of operations. While comparisons are n^2 always (all cases), the number of assignments is different (having cases). Try to discuss the cases from assignments perspective. ------------------------------------------------------------------------------------------------------ *** Context: *** In the Selection Sort algorithm, we first find the smallest element and bring it to the array position 0. Next, we bring the second smallest element and put it in the position 1...etc. By the ith iteration, the with smallest element comes at the ith position. We will need (n-1) iterations in total. When the n-1 elements are in their appropriate locations, the nth element is automatically in the correct location. for (int i = 0; i < n -1; i++) } int index = i; for (int j = i + 1; j < n; j ++) { if (arr[j] < arr[index]) index = j; } // Swap the elements at locations I // and index int temp = arr[index]; arr[index] = arr[i]; arr[i] = temp; } The time complexity is the theta(n^2) because there are two loops. The space complexity is O(n), no extra space us needed. We are not using any auxiliary memory. Therefore, extra space is theta(1). The order of the elements in the array does not matter. The Best, worst, and average case complexities will ALL be theta(n^2) Best = Theta (n^2) Worst = Theta (n^2) Average = Theta (n^2) Please help me answer the following question from my professor, Your post is appropriate and corrcet, except for one statement which is inconsistent: "The space complexity is O(n), no extra space us needed. " O(n) contradicts no extra space. Please clarify. Class, As interaction contribution, you may try to answer the following question: Q: Indeed, the complexity is Theta(n^2) . However, there is a difference in number of operations. While comparisons are n^2 always (all cases), the number of assignments is different (having cases). Try to discuss the cases from assignments perspective.
Please help me answer the following question.
Your post is appropriate and correct, except for one statement which is inconsistent: "The space complexity is O(n), no extra space us needed. "
O(n) contradicts no extra space. Please clarify.
Class,
As interaction contribution, you may try to answer the following question:
Q: Indeed, the complexity is Theta(n^2) . However, there is a difference in number of operations. While comparisons are n^2 always (all cases), the number of assignments is different (having cases). Try to discuss the cases from assignments perspective.
------------------------------------------------------------------------------------------------------
*** Context: ***
In the Selection Sort
Next, we bring the second smallest element and put it in the position 1...etc.
By the ith iteration, the with smallest element comes at the ith position.
We will need (n-1) iterations in total. When the n-1 elements are in their appropriate locations, the nth element is automatically in the correct location.
for (int i = 0; i < n -1; i++)
}
int index = i;
for (int j = i + 1; j < n; j ++)
{
if (arr[j] < arr[index])
index = j;
}
// Swap the elements at locations I
// and index
int temp = arr[index];
arr[index] = arr[i];
arr[i] = temp;
}
The time complexity is the theta(n^2) because there are two loops.
The space complexity is O(n), no extra space us needed.
We are not using any auxiliary memory. Therefore, extra space is theta(1).
The order of the elements in the array does not matter.
The Best, worst, and average case complexities will ALL be theta(n^2)
Best = Theta (n^2)
Worst = Theta (n^2)
Average = Theta (n^2)
Please help me answer the following question from my professor,
Your post is appropriate and corrcet, except for one statement which is inconsistent: "The space complexity is O(n), no extra space us needed. "
O(n) contradicts no extra space. Please clarify.
Class,
As interaction contribution, you may try to answer the following question:
Q: Indeed, the complexity is Theta(n^2) . However, there is a difference in number of operations. While comparisons are n^2 always (all cases), the number of assignments is different (having cases). Try to discuss the cases from assignments perspective.
------------------------------------------------------------------------------------------------------
*** Context: ***
In the Selection Sort algorithm, we first find the smallest element and bring it to the array position 0.
Next, we bring the second smallest element and put it in the position 1...etc.
By the ith iteration, the with smallest element comes at the ith position.
We will need (n-1) iterations in total. When the n-1 elements are in their appropriate locations, the nth element is automatically in the correct location.
for (int i = 0; i < n -1; i++)
}
int index = i;
for (int j = i + 1; j < n; j ++)
{
if (arr[j] < arr[index])
index = j;
}
// Swap the elements at locations I
// and index
int temp = arr[index];
arr[index] = arr[i];
arr[i] = temp;
}
The time complexity is the theta(n^2) because there are two loops.
The space complexity is O(n), no extra space us needed.
We are not using any auxiliary memory. Therefore, extra space is theta(1).
The order of the elements in the array does not matter.
The Best, worst, and average case complexities will ALL be theta(n^2)
Best = Theta (n^2)
Worst = Theta (n^2)
Average = Theta (n^2)
Subject: Java Programming
Step by step
Solved in 2 steps
