CODEWITHSUNDEEP
algorithmdata-structures
ksw
ksw

Reputation: 41

I'm confused about space complexity

I'm a little confused about the space complexity. 

int fn_sum(int a[], int n){
    int result =0;          
    for(int i=0; i<n ; i++){
        result += a[i];
    }

    return result;
}

In this case, is the space complexity O(n) or O(1)? I think it uses only result,i variables so it is O(1). What's the answer?

Upvotes: 1

Views: 1462

Answers (4)

Daniel
Daniel

Reputation: 7724

(1) Space Complexity: how many memory do your algorithm allocate according to input size?

int fn_sum(int a[], int n){
    int result = 0;              //here you have 1 variable allocated       
    for(int i=0; i<n ; i++){
        result += a[i];
    }
    return result;
}

as the variable you created (result) is a single value (it's not a list, an array, etc.), your space complexity is O(1), since the space usage is constant, which means: it doesn't change according to the size of the inputs, it's just a single and constant value.

(2) Time Complexity: how do the number of operations of your algorithm relates to the size of the input?

int fn_sum(int a[], int n){      //the input is an array of size n
    int result = 0;              //1 variable definition operation = O(1)   
    for(int i=0; i<n ; i++){     //loop that will run n times whatever it has inside
        result += a[i];          //1 sum operation = O(1) that runs n times = n * O(1) = O(n)
    }
    return result;               //1 return operation = O(1)
}

all the operations you do take O(1) + O(n) + O(1) = O(n + 2) = O(n) time, following the rules of removing multiplicative and additive constants from the function.

Upvotes: 2

Boby Robert
Boby Robert

Reputation: 94

Another way to calculate space complexity is to analyze whether the memory required by your code scales/increases according to the input given.

Your input is int a[] with size being n. The only variable you have declared is result.

No matter what the size of n is, result is declared only once. It does not depend on the size of your input n.

Hence you can conclude your space complexity to be O(1).

Upvotes: 0

Patrick87
Patrick87

Reputation: 28302

If int means the 32-bit signed integer type, the space complexity is O(1) since you always allocate, use and return the same number of bits.

If this is just pseudocode and int means integers represented in their binary representations with no leading zeroes and maybe an extra sign bit (imagine doing this algorithm by hand), the analysis is more complicated.

If negatives are allowed, the best case is alternating positive and negative numbers so that the result never grows beyond a constant size - O(1) space.

If zero is allowed, an equally good case is to put zero in the whole array. This is also O(1).

If only positive numbers are allowed, the best case is more complicated. I expect the best case will see some number repeated n times. For the best case, we'll want the smallest representable number for the number of bits involved; so, I expect the number to be a power of 2. We can work out the sum in terms of n and the repeated number:

result = n * val
result size = log(result) = log(n * val) = log(n) + log(val)
input size = n*log(val) + log(n)

As val grows without bound, the log(val) term dominates in result size, and the n*log(val) term dominates in the input size; the best-case is thus like the multiplicative inverse of the input size, so also O(1).

The worst case should be had by choosing val to be as small as possible (we choose val = 1) and letting n grow without bound. In that case:

result = n
result size = log(n)
input size = 2 * log(n)

This time, the result size grows like half the input size as n grows. The worst-case space complexity is linear.

Upvotes: 1

JATothrim
JATothrim

Reputation: 852

I answer bit differently: Since memory space consumed by int fn_sum(int a[], int n) doesn't correlate with the number of input items its algorithmic complexity in this regard is O(1).

However runtime complexity is O(N) since it iterates over N items.

And yes, there are algorithms that consume more memory and get faster. Classic one is caching operations. https://en.wikipedia.org/wiki/Space_complexity

Upvotes: 1

Related Questions