By Theorem REF  the parallel dictionary query in step 2 takes worst case constant time. Finding the leftmost bit that is 1 takes constant time on the word RAM [1]}. The remaining operations are standard operations available in the model, so the procedure runs in constant time.
