Specifically O(n) means that if there's 2x as many items in the list, it'll takes *No more than* twice as long, if there's 50 times as many it'll take *No more than* 50 times as long. See the wikipedia article dreeves pointed out for more details

Edit (in bold above): It was pointed out that Big-O does represent the upper bound, so if there's twice as many elements in the list, insertion will take at *most* twice as long, and if there's 50 times as many elements, it would take at *most* 50 times as long.

If it was additionally Ω(n) (Big Omega of n) then it would take at *least* twice as long for a list that is twice as big. If your implementation is both O(n) and Ω(n), meaning that it'll take both at *least* and at *most* twice as long for a list twice as big, then it can be said to be Θ(n) (Big Theta of n), meaning that it'll take exactly twice as long if there are twice as many elements.

According to Wikipedia (and personal experience, being guilty of it myself) Big-O is often used where Big-Theta is what is meant. It would be technically correct to call your function O(n^n^n^n) because all Big-O says is that your function is no slower than that, but no one would actually say that other than to prove a point because it's not very useful and misleading information, despite it being technically accurate.

Nrefers to the number of items that are already in the list. Insertion is performed withO(N)means that in the worst case the whole list has to be walked through until the position is found where new element can be inserted so that the list after the insertion is sorted as well.