Space Complexity vs Time Complexity
I have been doing a lot of lc practice however I always almost struggle with space complexity when evaluating it. I slowly but surely realised not only your solution should be optimal in terms of time it should also be optimal in terms of space. So can the community please suggest me a good resource for learning this forte because most if not all courses are focused on time complexity.#tech #interviews #faang
The reason most university classes focus on time complexity and not so much on space complexity is because it's not that complex (see what I did there). You can have algorithms that have time complexities like O(A*B*log log C) and calculating that wouldn't be that straightforward. With space complexity, your space, given a particular input size, will usually be just constant, multiple or exponential times of the input size, and this is something you learn in middle school.
space complexity can also be log n
Yeah this guy is an idiot
Your solution should definitely be time optimal first. Then without sacrificing that, if you can find ways to use less memory then that’s a plus. I don’t think there’s a one size fits all answer to this, it really depends on the problem
Well, O(1) implies constant space or just utilizing the input you've been provided. O(n) means an additional amount of space which is equal to the input size - like a copy of the input array(1D). If you're building a graph using a matrix it's O(n^2) but if you use adjacency lists it's O(n + m)(n,m are # of vertices and edges). (Of course, this is a very quick answer typed up on a phone. But, solve more questions with data structures as the focus and you'll understand how to compute space complexity )
Hey, don't we include input size in space complexity? Like if we are traversing an array of size n then won't space complexity be O(n) but auxiliary space used would be O(1).
AFAIK when people talk about space complexity it is assumed you are talking about auxiliary space
Time complexity issues are more annoying to end user
Just like time complexity try to understand it in terms of operations. Searching in an array, do you need to store the values in an additional array, if yes how much space (in order of the input) does it take, can you do it without creating an additional array; what are the implicit operations you might be doing that adds to the space complexity (e.g recursion and adding to call stack).
Both might give valid solutions, more space optimal might be not creating an additional or using an iterative approach vs recursive. I don't think there is any central resource but study as many also as you can and understand each operation in terms of space and time. Sometimes one can be optimized over the other.
Appreciate the detailed breakdown and explanation.
Explain that gravity warps space-time
I haven’t come across any resource which explains space complexity in isolation, but there are many well written publications suggest - an algorithm must trade increased space usage with decreased execution time as memory now a days is very cheap. Also one has to have deep understanding of various DS and which one to choose over other while implementing … For example ‘Linked List’ can continue to expand without having to specify their size ahead of time unlike of Array - where one has to preload with initial Array size irrespective it is empty or has elements, and resizing Array is inefficient and will consume 2 X previous size every time you resize it … meaning more wastage of space and more time to resize !
Time is money. Space is not
Go try GPU programming where you have maximum ~36GB of global memory typically and people always want to run scientific simulations which are memory hogs you won’t be saying the same thing
following