Big O - In simple words, this describes how long an algorithm takes to run and how much space it takes. It expresses how the runtime quickly grows with respect to the input.
This is how we compare different algorithms's efficiency.
Some quick notes -
- N could be the actual input or the size of the input
- We always talk about the worst-case here
- We drop constants and less significant terms since as input grow infinitely large constants and less significant terms do not make much difference
Space complexity talks about memory or space. This measures, how memory grows as the input size increases. Usually, when we talk about space complexity, we're talking about additional space
The link I referred - https://www.interviewcake.com/article/java/big-o-notation-time-and-space-complexity
Interview tips - Always talk about time and space complexity at the end. This will earn you bonus points!
FAANG companies expect this even if they don't ask explicitly.
Some useful graphs -
Comments
Post a Comment