i am trying to do a study on Space complexity of bubble sort algorithm what i know that the Space complexity of bubble sort algorithm is O(1) given the below bubble sort algorithm how can i change the bubble sort aalgorthim code to make the space or memory complexity to O(n) or O(n square) , etc i need to understand where the space complexity playes a role ...thanks
public void bubbleSort(int[] arr) {
boolean swapped = true;
int j = 0;
int tmp;
while (swapped) {
swapped = false;
j++;
for (int i = 0; i < arr.length - j; i++) {
if (arr[i] > arr[i + 1]) {
tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
}
Tanu Khandelwal :
Bubble sort(A,n)\n for(i=n;i>=1;i--)\n for(j=1;j<=i-1;j++)\n if(a[j]>a[j+1])\n {\n t <- a[j]\n a[j] <- a[j+1]\n a[j+1] <- t\n }\n\nHere we show input variable and temporary variable for space complexity then i and j are input variable of which space complexity always be constant and temporary variable t always be show 1 so space complexity of bubble sort is o(1).",
2020-11-26T08:50:21
StoryTeller - Unslander Monica :
The space complexity is a measure of how much extra memory your algorithm requires.\n\nIf you were to allocate an extra array of size n (when n is the variable size of the input array), the space complexity would be O(n).",
2012-12-05T11:10:53
Peter Lawrey :
If you want to increase space complexity you just need to waste memory e.g. add some code to use more memory. \n\nIts decreasing space complexity which is hard.",
2012-12-05T11:09:40
amit :
I think it worths an answer, because it has some input on big O notation:\n\nYour algorithm already is O(n) and O(n^2) space \n\nThis is because O(1) is a subset of O(n) and both are subsets of O(n^2)\n\nWhy is it so?\nNote that O(f(n)) is a set of functions with \"asymptotic upper bound of f(n)\" (intuitive definition, not formal).\n\nThus, for each g(n)<h(n)<f(n), if h(n) is an asymptotic upper bound of g(n), then f(n) is also asymptotic upper bound of it.\n\nThus, if g(n) is in O(h(n)) - it is also in O(f(n))\nAnd in your case, if the complexity function T(n) is in O(1), it is also in O(n)",
2012-12-05T11:31:48
Ted T :
Your algorithm already is O(n) space, since you need at least n cells of memory",
2012-12-06T23:55:32
SBD :
Here space complexity of your algorithm is O(n) and Auxiliary Space complexity it O(1).\n\nIn general we do compare Auxiliary complexity. why ?\n\nMerge-Sort takes O(n) auxiliary space and Insertion sort requires O(1) auxiliary space Space complexity of these two sorting algorithms is O(n) though.",
2019-01-13T14:29:05