Woooow, this is sooo cool !!! I can’t unsee it anymore !! I just did one of the variations on paper (the subtraction one presented at the bottom of the wikipedia link), this is great !!
Im wondering though, this isnt totally free, is it ? I guess there’s an extra addition/subtraction calculation everytime you go from one cell to the next since instead of reading the next/prev pointer you now need to read a value and calculate the pointer from it, am i understanding this correctly ? (Not a computer scientist, so ive never had a formal algorithm class).
Very very very neat nonetheless, thank you very much ;)
The extra calculation doesn't change the theoretical asymptotic time complexity because O((k+1)f(n)) = O((k)f(n)) = O(f(n)). In a real computer most of the calculation time will be spent dealing with cache misses and reading from memory, especially in a linked list which is very easy to code in a cache-unfriendly manner. So it is basically free.
Im wondering though, this isnt totally free, is it ? I guess there’s an extra addition/subtraction calculation everytime you go from one cell to the next since instead of reading the next/prev pointer you now need to read a value and calculate the pointer from it, am i understanding this correctly ? (Not a computer scientist, so ive never had a formal algorithm class).
Very very very neat nonetheless, thank you very much ;)