It's O(log n) because Haskell is smart enough to implement exponentiation by repeated squaring and summing as appropriate? (There must be a better name for that.)