Difference between revisions of "Talk:TADM2E 3.11"
Brownslink (talk | contribs) (Space requirement really O(n**2)) |
m |
||
| (3 intermediate revisions by 3 users not shown) | |||
| 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? | ||
| + | |||
| + | 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 == | ||
| + | |||
| + | 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... | ||
Latest revision as of 10:13, 27 September 2019
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?
Well, i thought the same, but we cannot. It becomes clear when you think of the interface as below: $ find\_min( (x_1, x_2, .. x_n), i, j) $ So, the user supplied us the sequence, and they expect us to find the minimum of a sub-sequence of the given sequence. --Mytreya (talk) 10:11, 27 September 2019 (UTC)
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...
