« Analysis of space complexity for an algorithm
What is space complexity
It is space required as a function of n(input size) f(n)
Generally when are talking about space complexity, we are talking about auxiliary space i.e. the additional space you require. So if in a problem we are given an array of size n then we don't need to count this is space complexity.
It is the maximum space required by the program or function at any given point of time
In Above graph, 30mb will be the space required.
In Above function, maximum 4 mb is the space required at any given point of time as with each iteration, k is de-allocated and new k is allocated.
- In case of recursion:
Here n functions with their local storage are sitting idle waiting for the fact(0) to return result. Each function is storing local variables and at at which line further functions are called and other information(all this info takes constant space). At some point of time algorithm is using kn space maximum.
Space complexity in case of Bubble sort
In case of Bubble sort at any point of time maximum you are consuming couple of bytes(equivalent to constant space).
Space complexity in case of Binary search recursively
O(logn)
