Talk:TADM2E 3.11 - Revision history

Mytreya at 10:13, 27 September 2019

2019-09-27T10:13:58Z

Mytreya at 10:11, 27 September 2019

2019-09-27T10:11:47Z

Idealamz: /* a counterexample for 3.11 b */ new section

2017-12-06T19:33:57Z

‎a counterexample for 3.11 b: new section

SriPrasanna at 00:01, 6 April 2015

2015-04-06T00:01:59Z

Brownslink: Space requirement really O(n**2)

2015-02-01T23:38:55Z

Space requirement really O(n**2)

New page

For the answer given in part 2, the space required seems to be the sum from 1 to n of n which is n(n+1)/2. This gives O(n**2) for space requirements. Doesn't it?

@@ Line 5: / Line 5: @@
 Well, i thought the same, but we cannot. It becomes clear when you think of the interface as below:
-<math>find_min( (x_1, x_2, .. x_n), i, j)</math>
+<math>find\_min( (x_1, x_2, .. x_n), i, j)</math>
 So, the user supplied us the sequence, and they expect us to find the minimum of a sub-sequence of the given sequence.
 --[[User:Mytreya|Mytreya]] ([[User talk:Mytreya|talk]]) 10:11, 27 September 2019 (UTC)

← Older revision		Revision as of 10:11, 27 September 2019
Line 3:		Line 3:

	Why cant we just sort the input (array)? Will this not mean the smallest number between x and y is always x?		Why cant we just sort the input (array)? Will this not mean the smallest number between x and y is always x?
		+
		+	Well, i thought the same, but we cannot. It becomes clear when you think of the interface as below:
		+	<math>find_min( (x_1, x_2, .. x_n), i, j)</math>
		+	So, the user supplied us the sequence, and they expect us to find the minimum of a sub-sequence of the given sequence.
		+	--[[User:Mytreya\|Mytreya]] ([[User talk:Mytreya\|talk]]) 10:11, 27 September 2019 (UTC)

	== a counterexample for 3.11 b ==		== a counterexample for 3.11 b ==

← Older revision		Revision as of 19:33, 6 December 2017
Line 3:		Line 3:

	Why cant we just sort the input (array)? Will this not mean the smallest number between x and y is always x?		Why cant we just sort the input (array)? Will this not mean the smallest number between x and y is always x?
		+
		+	== a counterexample for 3.11 b ==
		+
		+	for this input = [0,1,...,98,99] and this query i = 1, j = 99.
		+
		+	the suggested algorithm will always span in both sides - right and left, so according to the suggested solution it will always split the task to 2.
		+	that means that if h is the height of the tree the query time is going to be O(2^h)
		+
		+	now h = log(n) so it's 2^log(n) = n
		+
		+	for O(n) cost we can simply iterate over all the values in the given range and find the minimum...

← Older revision		Revision as of 00:01, 6 April 2015
Line 1:		Line 1:
	For the answer given in part 2, the space required seems to be the sum from 1 to n of n which is n(n+1)/2. This gives O(n**2) for space requirements. Doesn't it?		For the answer given in part 2, the space required seems to be the sum from 1 to n of n which is n(n+1)/2. This gives O(n**2) for space requirements. Doesn't it?
		+
		+
		+	Why cant we just sort the input (array)? Will this not mean the smallest number between x and y is always x?