Space complexity-DAA.pptx

UML

1. SPACE COMPLEXITY NAME: MOUNIKA PIN: 21BQ5A0514

2. Introduction to space complexity Space complexity refers to the amount of memory or storage space required by an algorithm to solve a problem. Space complexity is usually measured in terms of the number of bits or bytes required to store the data used by the algorithm. This includes both the input data and any additional memory used by the algorithm during its execution.

3. CALCULATION OF SPACE COMPLEXITY FOR AN ALGORITHM Space complexity of an algorithm is sum of space required for fixed part of algorithm and space required for variable part of algorithm. Space Complexity = Space required for fixed part +Space required for variable part Space Complexity = Space required for fixed part + Space required for variable part To estimate the memory requirement we need to focus on two parts:  (1) A fixed part:  It is independent of the input size. It includes memory for instructions (code), constants, variables, etc. (2) A variable part:  It is dependent on the input size. It includes memory for recursion stack, referenced variables, etc.

4. Under fixed part, the space for the following is considered Code of algorithm Simple variables or local variables Defined constants   Under variable part, the space for the following is considered Variables whose size varies from one instance of the problem to another instance (arrays, structures and soon) Global or referenced variables Recursion stack   Recursion stack space is considered only for recursive algorithms. For each call of recursive algorithm, the following information is stored in recursion stack Values of formal parameters Values of local variables Return value

5. Example : Calculate space complexity of the following algorithm Algorithm Add(a, b) { c := a + b; write c; }   Space complexity=space for fixed part + space for variable part   Space for fixed part: Space for code=c words Space for simple variables=3 (a, b, c) words Space for defined constants=0 words  

6. Space for variable part: Space for arrays=0 words Space for global variables=0 words Space for recursion stack=0 words   Space complexity=c+3 +0+0+0+0=(c+3) words

7. Example : calculate space complexity for the following recursive algorithm Algorithm Rsum (a, n) // a is an array of size { if n = 0 then return 0; else   return a[n] + Rsum (a, n-1); }   Space for fixed part: Space for code=c words Space for simple variables=1 (n) word Space for defined constants=0 words  

8. Space for variable part: Space for arrays=n words Space for global variables=0 words Space for recursion stack=3(n+1) words   For each call of the algorithm, three values are stored in recursion stack (formal parameters: n, starting address of array and return value). The algorithm is called for n+1 times. Total space required by the recursion stack is (n+1)*3 words.   Space complexity = c+1+0+n+0+(n+1)3=(c+4n+4) words