CODEWITHSUNDEEP
space-complexity
Siddhesh Shinde
Siddhesh Shinde

Reputation: 33

How is the space complexity of below algorithm come out to be O(log n)

int[] findMinMax(int A[], int start, int end)
{
int max;
int min;
if ( start == end )
{
    max = A[start]
    min = A[start]
}
else if ( start + 1 == end )
{
    if ( A[start] < A[end] )
    {
        max = A[end]
        min = A[start]
    }
    else
    {
        max = A[start]
        min = A[end]
    }
}
else
{
    int mid = start + (end - start)/2
    int left[] = findMinMax(A, start, mid)
    int right[] = findMinMax(A, mid+1, end)
    if ( left[0] > right[0] )
        max = left[0]
    else
        max = right[0]
    if ( left[1] < right[1] )
        min = left[1]
    else
        min = right[1]
}
// By convention, we assume ans[0] as max and ans[1] as min
int ans[2] = {max, min}
 return ans
 }

On analysing the time complexity comes out to be O(n) using the master theorem for recursion. On looking through the pseudocode it's much clear that Divide & Conquer Algorithmic Paradigm is used. I'm facing difficulty with the space complexity part. Any help would be appreciated ?

Upvotes: 0

Views: 59

Answers (1)

shree.pat18
shree.pat18

Reputation: 21757

Your arrays left and right get populated by the recursive calls to your function. Since the input to these calls keeps getting halved in size with each call, you will only need log n number of calls before you get to the base case where you do not need to populate them at all. The bound on auxiliary space used is therefore O(log n).

Upvotes: 1

Related Questions