CODEWITHSUNDEEP
algorithmspace-complexity
Rahul Arora
Rahul Arora

Reputation: 4533

Space complexity of an algorithm

Example1: Given an input of array A with n elements.

See the algo below:

Algo(A, I, n)
{
    int i, j = 100;
    for (i = 1 to j)
        A[i] = 0;
}

Space complexity = Extra space required by variable i + variable 'j'

In this case my space complexity is: O(1) => constant

Example2: Array of size n given as input

A(A,I,n)
{
    int i;
    create B[n]; //create a new array B with same number of elements
    for(i = 1 to n)
      B[i] = A[i]
}

Space complexity in this case: Extra space taken by i + new Array B => 1 + n => O(n)

Even if I used 5 variables here space complexity will still be O(n).

If as per computer science my space complexity is always constant for first and O(n) for second even if I was using 10 variables in the above algo, why is it always advised to make programs using less number of variables?

I do understand that in practical scenarios it makes the code more readable and easier to debug etc.

But looking for an answer in terms of space complexity only here.

Upvotes: 1

Views: 989

Answers (2)

Geeky
Geeky

Reputation: 7496

For this code snippet

Algo(A, I, n)
{
    int i, j = 100;
    for (i = 1 to j)
        A[i] = 0;
}

Space Complexity is: O(1) for the array and constant space for the two variables i and j

It is always advised to use less variables because ,each variable occupies constant space ,if you have 'k' variables.k variables will use k*constant space ,if lets consider each variable is of type int so int occupies 2 bytes so k*2bytes,lets take k as 10 so it 20bytes here

It is as similar as using int A[10] =>20 bytes space complexity

I hope you understand

Upvotes: 0

user1726343
user1726343

Reputation:

Big O complexity is not the be-all end-all consideration in analysis of performance. It is all about the constants that you are dropping when you look at asymptotic (big O) complexity. Two algorithms can have the same big-O complexity and yet one can be thousands of times more expensive than the other.

E.g. if one approach to solving some problem always takes 10s flat, and another approach takes 3000s flat, regardless of input size, they both have O(1) time complexity. Of course, that doesn't really mean both are equally good; using the latter approach if there is no real benefit is simply a massive waste of time.

This is not to say performance is the only, or even the primary consideration when someone advises you to be economical with your use of local variables. Other considerations like readability, or avoidance of subtle bugs are also factors.

Upvotes: 1

Related Questions