3 ms·
Why is the lower bound N/3 and not N/2? Doesn’t the set of all odd numbers make the lower bound N/2?
by VladVladikoff 1y ago
Why is the lower bound N/3 and not N/2? Doesn’t the set of all odd numbers make the lower bound N/2?
- Bootvis 1y agoN/3 + log log N holds for any arbitrary set, not just for 1 … N or something.
- hiddencost 1y agoAn adversary first gives you any set, and then you have to find a subset. They could give you only even numbers.
- VladVladikoff 1y agoOhhhh ok thanks!