Definition of complexity

I am going to start with this definition because I think it is the most important topic that is missing in the vast majority of coding courses.

Let's define complexity as the number of repeated operations, so in order to count out loud from 1 to 100, it has a complexity of 100, because you are saying a number 100 times. Easy.


Now imagine you have N boxes and you want to check which box has wallaby plushies, how many boxes should you open to know?

Well, it might be the first box, maybe the 25th, but it could be even the last one, we do not know. But something is sure, it is at most N boxes. So we can say that the complexity of this problem is N because you can not be sure that you will find it before N actions.


Now, you have N boxes, each one with at most M wallaby plushies, and you want to check how many plushies were actually kangaroo ones (a lot of people confuse them). How many plushies should you check to know the number of miss-packed ones?

Well, you must check each plushie, and there are at most N*M plushies. So we can say that the complexity of this problem is N*M because you can not say that you will use less than N*M checks to verify all of them.


And what about if you want to check if there are two boxes with the same number of plushies? You will need to check box by box, counting the plushies and when you find a box with the same number as a previous one, you will scream "Eureka! There are 2 boxes with the same number!" (yeah, super useful fact).

Now we can be sure that the complexity of this problem is N*M, but how many numbers will you need to remember in order to find the 2 special boxes?

You will need to remember the numbers of the previous boxes, and there is a case when the special boxes are the first and last ones, in that case, you will need to "storage" in your head the N-1 previous numbers. So, to be able to solve this problem, you will need N-1 free spaces in your memory. So let's say this problem has a space complexity of N. The "-1" is been omitting because N can be really big and a "-1" will not seem to affect it.


Now we can briefly define "time complexity" as how many times an action will be made, and "space complexity" as how many things you will need to save/storage. At the end of the Python section you will find a post that takes this to a deeper level, but for now, just keep the idea that "the less complexity in time and memory you code, the better it is".