here i have written some different cases of functions that have array as input i need help to determine if reasoning behind my answers is correct (i have put question marks on the cases im having difficulty with)
case 1:
algo(arr[],n){
//does nothing
}
Space = (0) + 0 = O(1)
Auxiliary Space = 0 = O(1)
(reason: storage allocated for inputs havent been worked on and no temporary storage declared inside the function)
case 2:
algo(arr[],n){
int i;
}
Space = (0) + 1 = O(1)
Auxiliary Space = 1 = O(1)
(reason: storage allocated for inputs havent been worked on and 1 temporary storage for variable i is needed)
case 3:
algo(arr[],n){
int i;
for(i=0; i<n ; i++){
//does nothing
}
}
Space = (1) + 1 = O(1)
Auxiliary Space = 1 = O(1)
(reason: storage for variable n is being worked on and 1 temp storage needed for variable i is needed)
case 4:
where arr[] is an array of size L where L > n
algo(arr[],n){
int i;
for(i=0;i<n;i++){
arr[i] = i;
}
}
Space = (1 + n) + 1 = O(n)
Auxiliary Space = 1 = O(1)
(reason: 1 storage for variable n and n storages for arr[0]....arr[n-1] is being worked on and 1 temp storage for variable i is needed)
case 5:??
where arr[] is an array of size L where L > n
algo(arr[],n){
arr[n]=n;
}
Space = (1 + 1) + 0 = O(1)
Auxiliary Space = 0 = O(1)
(reason: 1 storage for variable n is being worked on and only 1 storage will always be worked on in arr[] regardless of the value of n, no temporary storage was declared)
case 6:??
where arr[] is an array of size L where L > i
algo(arr[],n){
int i = 1;
arr[i]=i;
}
Space = (1) + 1 = O(1)
Auxiliary Space = 1 = O(1)
(reason: only 1 storage will always be worked on in arr[] which is always in arr[i] and 1 temp storage needed for i)
case 7:??
where arr[] is an array of size L where L > n
algo(arr[],n){
int i;
for(i=0;i<n;i++){
// does nothing
}
arr[n] = n;
}
Space = (1 + 1) + 1 = O(1)
Auxiliary Space = 1 = O(1)
(reason: 1 storage for variable n is being worked on and only 1 storage will always be worked on in arr[] regardless of the value of n, 1 temporary storage was declared for variable i)
case 8:??
where arr[] is an array of size L where L > i
algo(arr[],n){
int i;
for(i=0;i<n;i++){
// does nothing
}
i = 1;
arr[i] = i;
}
Space = (1 + 1) + 1 = O(1)
Auxiliary Space = 1 = O(1)
(reason: only 1 storage will always be worked on in arr[] which is always in arr[i], 1 storage for variable n being worked on, and 1 temp storage needed for variable i)
case 9:
where arr1[] is an array of size m
algo(arr1[],n){
int arr2[n];
}
Space = (1) + n = O(n)
Auxiliary Space = n = O(n)
(reason: 1 storage for variable n being worked on, n temporary storage needed for arr2[])
case 10:??
where arr1[] is an array of size L
algo(arr1[],n){
int m=1;
int arr2[m];
}
Space = (0) + 1 + m = O(m)
Auxiliary Space = 1 + m = O(m)
(reason: 1 temporary storage needed for variable m and m temporary storage needed for arr2[])
or
Space = (0) + 1 + 1 = O(1)
Auxiliary Space = 1 + 1 = O(1)
(reason: 1 temporary storage needed for variable m and since m is a constant the space required for arr2[] always going to be some constant c)
case 11:??
algo(arr1[],n){
int i;
int m=10;
int arr2[m];
for(i=0;i<m;i++){
arr2[i]= i;
}
}
Space = (0) + 1 + 1 + 1 = O(1)
Auxiliary Space = 1 + 1 + 1 = O(1)
(reason: 1 temporary storage needed for variable m, 1 temp storage for variable i and since m is a constant the space required for arr2[] always going to be some constant c)
case 12:
where arr1[] is an array of size L where L > n and then arr2[] is an array of size K where K > m
algo(arr1[],n, arr2[], m){
int i;
for(i=0;i<n;i++){
arr1[i]= i;
}
for(i=0;i<m;i++){
arr2[i]= i;
}
}
Space = (1 + n + 1 + m) + 1 = O(n + m)
Auxiliary Space = 1 = O(1)
(reason: 2 storage for var n and m being worked on, n storage for arr1, m storage for arr2 and 1 storage needed for var i)
case 13:??
where arr1[] is an array of size L and L > n
algo(arr1[],n){
int i;
int m=10;
int arr2[m];
for(i=0;i<n;i++){
arr1[i]= i;
}
for(i=0;i<m;i++){
arr2[i]= i;
}
}
Space = (1 + n) + 1 + 1 + 1 = O(n)
Auxiliary Space = 1 + 1 + 1 = O(1)
(reason: 2 spaces needed for variable i and m, constant m space needed for arr2, 1 space being worked on for var n and n space being worked on for arr1)
case 14:
algo(arr1[],n){
int arr2[10];
}
Space = (0) + 1 = O(1)
Auxiliary Space = 1 = O(1)
(reason: 10 spaces is always required to declare arr2 whenever the function is called)
ok, instead of addressing each case one by one, I will try to help you understand space complexity which will probably answer all your doubts.
Space complexity of a method is defined as how much amount of extra space your method uses, as the input grows, to run an algorithm of your choice.
algo(arr[],n){
}
algo(arr1[],n, arr2[], m){
}
In the above method definitions-
If I only operate on parameter variables along with some extra variables like-
int a=1,b=10,c=99;
int[] new_array = new int[1000];
int m=1; int[] arr = new int[m];
All these will still be considered as O(1) space complexity. As you can see, the
number of variables and size of them doesn't change regardless of how big my input is.
If I declare additional variables which grows with input like-
int[] sum = new int[n];
int[][] sum = new int[n][n];
int[][] sum = new int[n][m];
As you can notice, the size of my array depends on n which was the parameter that was
passed to the method. Here, if my input array size happens to be 1000000000, my
method will also consume 1000000000 making it O(n) in space.
int[] sum = new int[n]; takes
O(n)space since size depends onnint[][] sum = new int[n][n]; takes O(n2) space since it has
nrows andncolumns.int[][] sum = new int[n][m]; takes
O(n*m)space since it hasnrows andmcolumns.
int[][] arr = new int[n][]; for(int i=0;i<n;++i){ arr[i] = new int[i+1]; }
The above code snippet does the following-
n rows.Example-
1st row - 1 column.
2nd row - 2 columns.
3rd row - 3 columns.
4th row - 4 columns.
and so on and so forth till
nth row - n columns.
The space complexity of the above code is O(n2). Reason is because, in asymptotic notation, we care more about the worst case scenario. Here,regardless of other rows,for the nth row, we are having n columns and this grows with input as well.
I hope this made you clear about space complexity.