Difference between revisions of "Talk:TADM2E 3.13"
From Algorithm Wiki
| (One intermediate revision by the same user not shown) | |||
| 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): | + | brandon.arnold (7/8/2017): It absolutely differs from the requirements, though my edition states at most an "additional array of size n," which is more stringent a requirement than O(n) memory usage. Were it the latter case, a binary tree would satisfy this (and no, it is not O(nlogn); a binary tree with n leaves is O(n) space). I have just edited it to include the solution. |
Latest revision as of 02:36, 9 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): It absolutely differs from the requirements, though my edition states at most an "additional array of size n," which is more stringent a requirement than O(n) memory usage. Were it the latter case, a binary tree would satisfy this (and no, it is not O(nlogn); a binary tree with n leaves is O(n) space). I have just edited it to include the solution.
