Computer Science Engineering (CSE)  >  Algorithms  >  Space Complexity

Space Complexity Notes | Study Algorithms - Computer Science Engineering (CSE)

Document Description: Space Complexity for Computer Science Engineering (CSE) 2022 is part of Algorithms preparation. The notes and questions for Space Complexity have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Space Complexity covers topics like What does ‘Space Complexity’ mean? and Space Complexity Example, for Computer Science Engineering (CSE) 2022 Exam. Find important definitions, questions, notes, meanings, examples, exercises and tests below for Space Complexity.

Introduction of Space Complexity in English is available as part of our Algorithms for Computer Science Engineering (CSE) & Space Complexity in Hindi for Algorithms course. Download more important topics related with notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Computer Science Engineering (CSE): Space Complexity Notes | Study Algorithms - Computer Science Engineering (CSE)
Table of contents
What does ‘Space Complexity’ mean?
1 Crore+ students have signed up on EduRev. Have you?

What does ‘Space Complexity’ mean?

Space Complexity: The term Space Complexity is misused for Auxiliary Space at many places. Following are the correct definitions of Auxiliary Space and Space Complexity.
Auxiliary Space is the extra space or temporary space used by an algorithm.
Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size. Space complexity includes both Auxiliary space and space used by input.
For example, if we want to compare standard sorting algorithms on the basis of space, then Auxiliary Space would be a better criteria than Space Complexity. Merge Sort uses O(n) auxiliary space, Insertion sort and Heap Sort use O(1) auxiliary space. Space complexity of all these sorting algorithms is O(n) though.
Space complexity is a parallel concept to time complexity. If we need to create an array of size n, this will require O(n) space. If we create a two dimensional array of size n*n, this will require O(n2) space.
In recursive calls stack space also counts.
Example:
    int add (int n){
          if (n <= 0){
            return 0;
   }
   return n + add (n - 1);
}
Here each call add a level to the stack:
1.  add(4)
2.    -> add(3)
3.      -> add(2)
4.        -> add(1)
5.          -> add(0)
Each of these calls is added to call stack and takes up actual memory. So it take O(n) space.
However just because you have n calls total doesn’t mean it takes O(n) space.
Look at the below function:
int addSequence (int n){
        int sum = 0;
        for (int i = 0; i < n; i++){
             sum+ = pairSum(i, i + 1);
        }
        return sum;
}
int paiSem(int x, int y){
         return x + y;
}
There will be roughly O(n) calls to pairSum. However, those calls do not exist simultaneously on the call stack, so you only need O(1) space.

Note: It’s necessary to mention that space complexity depends on a variety of things such as the programming language, the compiler, or even the machine running the algorithm.

The document Space Complexity Notes | Study Algorithms - Computer Science Engineering (CSE) is a part of the Computer Science Engineering (CSE) Course Algorithms.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

Related Searches

Important questions

,

Semester Notes

,

Space Complexity Notes | Study Algorithms - Computer Science Engineering (CSE)

,

Extra Questions

,

ppt

,

study material

,

video lectures

,

MCQs

,

pdf

,

past year papers

,

Viva Questions

,

Previous Year Questions with Solutions

,

Sample Paper

,

mock tests for examination

,

Objective type Questions

,

Space Complexity Notes | Study Algorithms - Computer Science Engineering (CSE)

,

shortcuts and tricks

,

Exam

,

Space Complexity Notes | Study Algorithms - Computer Science Engineering (CSE)

,

Free

,

practice quizzes

,

Summary

;