Talk:TADM2E 3.13 - Revision history

Brandon.arnold at 02:36, 9 July 2017

2017-07-09T02:36:10Z

Brandon.arnold at 18:13, 8 July 2017

2017-07-08T18:13:34Z

Brandon.arnold at 18:00, 8 July 2017

2017-07-08T18:00:51Z

NullObjectPtr: 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..."

2015-01-11T23:07:37Z

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..."

New page

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?

← Older revision		Revision as of 02:36, 9 July 2017
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): 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). ~~Anyway, this is wrong~~.	+	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.

← Older revision		Revision as of 18:13, 8 July 2017
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.	+	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). Anyway, this is wrong.

← Older revision		Revision as of 18:00, 8 July 2017
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.