# Difference between revisions of "Talk:TADM2E 3.11"

From Algorithm Wiki

SriPrasanna (Talk | contribs) |
(→a counterexample for 3.11 b: new section) |
||

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

## Revision as of 19:33, 6 December 2017

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?

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