Before revision:  We also investigate intermediate cases between O(1) and O(log log n ).
After revision:  We also investigate intermediate cases between O(1) and O(log log |w| ).