Prove by induction:
Claim: can make n outcomes into n columns where each column has at most two outcomes
ohmygearbox
Basically for n outcomes, pick one which has less than average height and put it into a bucket with the top portion of an outcome that has greater than average height, creating a column in your solution set. This way you have n - 1 remaining columns
jesshuifeng
I still don't understand why O(1)?
atomicapple0
i think you use induction
PsychotiK
With at most two outcomes per column, once we randomly sample from the N columns which is O(1), we can then randomly sample again and check to see if it is less than or greater than the threshold between the colors if there are 2. This is also an O(1) operation.
AL_
can someone explain the induction proof again?
Evanolott
^ about the induction proof.
doberdog91
PsychotiK's explanation makes sense
jin
What is the complexity of the pre-processing? Is it like O(nlog(n))?
haotingl
induction?
notme
It is possible in general as you can use induction. The newest block you can change the width of in order to conform the height to the height of the rectangle you get from the IH.
Prove by induction: Claim: can make n outcomes into n columns where each column has at most two outcomes
Basically for n outcomes, pick one which has less than average height and put it into a bucket with the top portion of an outcome that has greater than average height, creating a column in your solution set. This way you have n - 1 remaining columns
I still don't understand why O(1)?
i think you use induction
With at most two outcomes per column, once we randomly sample from the N columns which is O(1), we can then randomly sample again and check to see if it is less than or greater than the threshold between the colors if there are 2. This is also an O(1) operation.
can someone explain the induction proof again?
^ about the induction proof.
PsychotiK's explanation makes sense
What is the complexity of the pre-processing? Is it like O(nlog(n))?
induction?
It is possible in general as you can use induction. The newest block you can change the width of in order to conform the height to the height of the rectangle you get from the IH.