4 ms·
The best known algorithms, say relabel-to-front, is O(m^1.5) and the paper proposes an algorithm which is O(m^(1+o(1)). Here, 1.5 is fixed but 1+o(1) can be any
by gauddasa 4y ago
The best known algorithms, say relabel-to-front, is O(m^1.5) and the paper proposes an algorithm which is O(m^(1+o(1)). Here, 1.5 is fixed but 1+o(1) can be anywhere between 1 and 2 based on your luck, and should be 1.5 on an average over variety of inputs. Still no free lunch.
- nephanth 4y ago> based on your luck Uh, no, based on the size of your input. o(1) means something that goes to 0 as m gets bigger, it has nothing to do with randomness.