In any given function in java what do I need to look for in

In any given function in java, what do I need to look for in order to determine its space complexity? thank you

Solution

You need to identify that is there any type of memory your creating locally in function to process current execution of the function.

Type of memory generally can be created in function are:

1. local variables . ex int a, double y, String z etc : Space complexity : O(1) => constant

2. An Array, ArrayList, LinkedList, HashMap etc of size K => Space complexity : O(k)

For example:

void merge(int arr[], int l, int m, int r)
{
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;

/* Create temp arrays */
int L[] = new int [n1]; // WE ARE CREATING EXTRA MEMORY
int R[] = new int [n2]; // WE ARE CREATING EXTRA MEMORY

/*Copy data to temp arrays*/
for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];


/* Merge the temp arrays */

// Initial indexes of first and second subarrays
int i = 0, j = 0;

// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}

/* Copy remaining elements of L[] if any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}

/* Copy remaining elements of L[] if any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}

Here you can see I am creating two array of size : n1 and n2 , ni+n2 = n , So space complexity: O(n)

We generally ignore those memory that takes constnt time