what is Big O notion n CS??

It shows how an algorithm scales.

O(n2):

• 1 item: 1 second
• 10 items: 100 seconds
• 100 items: 10000 seconds

Notice that the number of items increases by a factor of 10, but the time increases by a factor of 102. Basically, n=10 and so O(n2) gives us the scaling factor n2 which is 102.

O(n):

• 1 item: 1 second
• 10 items: 10 seconds
• 100 items: 100 seconds

This time the number of items increases by a factor of 10, and so does the time. n=10 and so O(n)'s scaling factor is 10.

O(1):

• 1 item: 1 second
• 10 items: 1 second
• 100 items: 1 second

The number of items is still increasing by a factor of 10, but the scaling factor of O(1) is always 1.

That's the gist of it. They reduce the maths down so it might not be exactly n2 or whatever they say it is, but that'll be the dominating factor in the scaling.