What?
When talking about space complexity, it's common that we hear the term 'Auxiliary space complexity'. This refers to the space required by the algorithm (not the space taken by inputs).
Why?
While it might be more pressing at some cases to look at time complexity, there will be times when you need to consider the environment in which your code will be executed and whether you will have the resources to do so.
Important tips to look out for
- Primitives are constant space (booleans, numbers, undefined, null)
- Strings require O(n) space (where n is the string length)
- Reference types are usually O(n) too, where n is either the length for arrays or number of keys for objects
In space complexity, we also use logarithms to express performance. So whenever you see O(log n) it's safe to say we're talking about space, not time complexity.
About logarithms
A logarithm is the inverse of exponentiation. The logarithm of a number roughly measures the number of times you can divide that number by 2 before you get a value that’s less than or equal to one.
Where can we expect to see logarithms?
Certain searching algorithms have logarithmic time complexity.
Efficient sorting algorithms involve logarithms.
Recursion sometimes might involve logarithmic space complexity.
So, where does this leave us?
To sum it up,
-Big O notation is used to analyze algorithm performance.
-It can give us a high level of understanding of the time or space complexity of it.
-It cares about general trends, not details.
-Time or space complexity depends only on the algorithm, not the hardware where it’s running.
Got something to add? Please feel free to reach out for any question, comment or meme.
Top comments (0)