Hacker News new | past | comments | ask | show | jobs | submit login

The value i can take an a priori unbounded amount of memory.

It should be noted, so can the value n, but in defining regular languages in this way, we allow our O(1) memory algorithms to be fed the characters of an a priori unbounded input string one by one sequentially.




Yeah, the O(1) refers to the size of the EXTRA memory you need, aside from the input. Defining it any other way would be strange. So, for instance, binary search over a sorted list needs O(log n) of memory (for the same reason as the prime algorithm, the pointer in the array is size O(log n) of the size of the array), even though the input is O(n).


Yup. Note that the method of specifically being fed the input sequentially, one by one, means that, for example, "Strings of odd length whose middle character is 'X'" does not comprise a regular language, even though one might naively reason this to be trivial to detect with O(1) memory ("Just go look at the middle character!").




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: