News for hackers. Stuff that matters.
Re:Tree traversal without recursion: the tree as a state mac... by pavas on Tuesday September 03, 2019 @09:09AM (#20866089)
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.
Re:Tree traversal without recursion: the tree as a state mac... by globuous on Tuesday September 03, 2019 @09:19AM (#20866201)
Thank you very much for this explanation !