First, I've noticed most of the time people omit what exactly n
represents in big O notation.
Yes, that is indeed a bad habit. In general, when you analyze complexity, you must specify:
- Are you talking about space complexity, step complexity, time complexity?
- Are you talking about best-case, worst-case, amortized worst-case, average case, expected case?
- What is your machine model? (I.e. what operations exist?)
- What is your cost model? (How long do those operations take?)
- What are you actually counting? (Comparisons, stores, loads, arithmetic operations, bit operations, etc.)
- How do you define "length of the input"? (Number of elements, number of bits, etc.)
- What is the distribution of your inputs? (In case of average or expected complexity.)
Usually it's related to the input, but it may be the value or length in bits or something else.
For data structures, it is usually the number of elements. For strings, it already gets trickier: is it the number of bytes, number of octets, number of `chars, number of code points, number of characters, number of graphemes, number of grapheme clusters?
One thing that catches many people out is that for numbers, it is usually not the magnitude, it is the length (i.e. the number of "digits" or bits), which is the logarithm of the magnitude.
Am I right that it's usually inferred from context?
Indeed. However, as mentioned above, for numbers, it is often inferred wrong.
The reason why we usually use the length of numbers is that arithmetic operations depend on the number of digits, not on the magnitude of the number: adding 1+1 take the same time as adding 4+4, but adding 10+10 takes twice as long. Adding 4999+5000 doesn't take 5000 times as long as adding 1+1, it only takes 4 times as long.
For example given in an array of 100 elements you know the value 50 appears and would like to find its index. That would be O(n) because the array would have to be traversed.
No, it would not. O(1) means the number of comparisons (which is what we are usually counting when talking about "searching") is bounded by a constant. In your example, you will never need more than 100 comparisons, therefore the number of comparisons is bounded by 100, which is a constant.
Therefore, the time complexity is O(100), which is the same as O(1).