The recursion assumes that log(n) > w; if log(n) <= w, then you're in the base case and it's O(n).