@mallard said:
@vt_mruhlin said:
@mallard said:
Thus they are limited to 255 characters. Their main advantages were being able to find the length in O(1) time
It's been a while since algorithms class in college, but if I'm not mistaken....If we know the length of the buffer, the maximum search time for that \0 is 256. I was always told that doing big-oh notation, constants don't generally matter. i.e. O(2n) is considered more or less equivalent to O(n), so O(256) might as well be O(1).
Course if all your code does is find th length of 1000 strings, you might notice that it takes 256 times longer in the extreme case, but generally speaking you're not going to notice a performance hit from that.
In my understanding O(1) means that the algorithm runs in constant time, meaning it takes the same amount of time every time (yes, O(256), O(99999), etc are all equivelent to O(1)). Since the algorithm for finding the length of a pascal string is simply "read the first byte", then it is contstant. The fact that pascal strings are limited to 256 characters is because their size must fit in a single byte, but you could have pascal-like strings using any amount of bytes to store the length and they would still have an O(1) time to find the length.
This is in contrast to C strings, where the algorithm is "read every byte until you find '\0'" e.g. O(n). If you know the buffer size of the C string then it is still O(n), except that n is now the buffer size, not the string length.
Sorry, both wrong. The O(f(n)) notation is only for the case where n can grow without bounds. Here, n <= 255, so it is meaningless to speak of what happens when n goes to infinity.