CODEWITHSUNDEEP
time-complexityspace-complexity
Shorya Sharma
Shorya Sharma

Reputation: 457

Why is the time complexity of the below snippet O(n) while the space complexity is O(1)

The below-given code has a space complexity of O(1). I know it has something to do with the call stack but I am unable to visualize it correctly. If somebody could make me understand this a little bit clearer that would be great. 

int pairSumSequence(int n) {
    int sum = 0;
    for (int i = 0;i < n; i++) {
        sum += pairSum(i, i + l);
    }
    return sum;
}

int pairSum(int a, int b) {

 return a + b;

}

Upvotes: 1

Views: 305

Answers (2)

bezirganyan
bezirganyan

Reputation: 425

Time/space complexity O(1) means a constant complexity, and the constant is not necessarily 1, it can be arbitrary number, but it has to be constant and not dependent from n. For example if you always had 1000 variables (independent from n), it would still give you O(1). Sometimes it may even happen that the constant will be so big compared to your n that O(n) would be much better than O(1) with that constant.

Now in your case, your time complexity is O(n) because you enter the loop n times and each loop has constant time complexity, so it is linearly dependent from your n. Your space complexity, however, is independent from n (you always have the same number of variables kept) and is constant, hence it will be O(1)

Upvotes: 2

Tommaso Fontana
Tommaso Fontana

Reputation: 730

How much space does it needs in relation to the value of n?

The only variable used is sum. sum doesn't change with regards to n, therefore it's constant.

If it's constant then it's O(1)

How many instructions will it execute in relation to the value of n?

Let's first simplify the code, then analyze it row by row.

int pairSumSequence(int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += 2 * i + l;
    }
    return sum;
}

The declaration and initialization of a variable take constant time and doesn't change with the value of n. Therefore this line is O(1).

int sum = 0;

Similarly returning a value takes constant time so it's also O(1)

return sum;

Finally, let's analyze the inside of the for:

sum += 2 * i + l;

This is also constant time since it's basically one multiplication and two sums. Again O(1). But this O(1) it's called inside a for:

for (int i = 0; i < n; i++) {
   sum += 2 * i + l;
}

This for loop will execute exactly n times. Therefore the total complexity of this function is:

C = O(1) + n * O(1) + O(1) = O(n)

Meaning that this function will take time proportional to the value of n.

Upvotes: 3

Related Questions