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.
[ Parent
| on HN ]