The Ultimate Big O Notation Tutorial (Time & Space Complexity For Algorithms)

Try Our Full Platform: nas.io/backtobackswe
📹 Intuitive Video Explanations
❓New Unseen Questions
🔎 Get All Solutions


Big O notation is very important for software engineering interviews. It really shows your capacity to critically think like an engineer.

The question that Big O answers is this: “how does the speed of this algorithm SCALE as the input to the system SCALES." That is it. It is a question of scale, not precise numbers. This is why we drop constants.

More precisely it is saying that if we give this algorithm VERY LARGE input, what will the UPPER BOUND of the runtime be? What will that tail behaviour be dictated by?

We say O(N) but what is n? Never say "n" without knowing what n is. Know what n is. Is it the string length? Is it the array length? Is it the number of nodes in the tree? What is it?

When we talk Big Oh we normally calculate the worst case and state that as the time complexity, hence giving it an upper bound that it cannot cross and hugs closely.

Space is calculated just like time complexity, do not be confused, but the question shifts to: “how does the space usage of this algorithm SCALE as the input to the system SCALES."

I know you want to memorize the "shape" and "pattern" of certain code but do not do this. Understand what is happening.

You will actually need to know what is going on to know them in their worst, average, and best case (although we care most about the average and worst).

It will help you find the optimal solution if you know the best complexity you can reach, it implies a method you can use that famously has that time complexity.

If you hear log(n) you know that the solution will use binary search or some algorithm that halves the input somehow...

In an interview you can't guess and that is the whole point of this, you will be put on the spot and have to explain. Explain confidently, be precise.

If you don't understand why something has the complexity it has don't be ok with not understanding, understand it, find out why and really think about what is happening. This will make you a stronger thinker and be able to tackle harder and harder problems.

Also, recursive and backtracking complexities are harder to calculate so just practice, those come with time and experience. Don't be discouraged...

+++++++++++++++++++++++++++++++++++++++++++++++++++

HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw