On the word RAM model of computation the complexity of the problem is well-understood with the following tight upper and lower bound on the time for operations given by Pătraşcu and Thorup [1]}.
\(\Theta \left(\max \left[1, \min \left\lbrace \log _w n,\frac{\log \frac{w}{\log w}}{\log \left( \log \frac{w}{\log w} / \log \frac{\log n}{\log w}\right)},\log \frac{\log (2^w - n)}{\log w}\right\rbrace \right]\right).\) 
