3 ms·
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 wikipedi
by globuous 7y ago
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 ;)
- pavas 7y agoThe 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.
- globuous 7y agoThank you very much for this explanation !