Difference between revisions of "Talk:TADM2E 3.13"
From Algorithm Wiki
(Created page with "Doesn't this solution violate the condition that we are restricted to O(n) memory usage? If the tree has N leaf nodes, and is a perfectly balanced binary tree, there would be...") |
|||
| Line 1: | Line 1: | ||
Doesn't this solution violate the condition that we are restricted to O(n) memory usage? If the tree has N leaf nodes, and is a perfectly balanced binary tree, there would be a total of N log N nodes and O( n log n ) memory used. Correct? | Doesn't this solution violate the condition that we are restricted to O(n) memory usage? If the tree has N leaf nodes, and is a perfectly balanced binary tree, there would be a total of N log N nodes and O( n log n ) memory used. Correct? | ||
| + | |||
| + | brandon.arnold (7/8/2017): Absolutely, I saw the same O(nlogn) approach but could not improve on it, and came here to see the correct one. This is wrong. | ||
Revision as of 18:00, 8 July 2017
Doesn't this solution violate the condition that we are restricted to O(n) memory usage? If the tree has N leaf nodes, and is a perfectly balanced binary tree, there would be a total of N log N nodes and O( n log n ) memory used. Correct?
brandon.arnold (7/8/2017): Absolutely, I saw the same O(nlogn) approach but could not improve on it, and came here to see the correct one. This is wrong.
