Size of the observable universe is constant. And maximization by exhaustive search requires touching every possible state. So yes, it is O(1). This is explained in Marcus' Ph.D. thesis, I believe.
If he says so, I should admit I'm wrong, but maybe not just yet.
This way of thinking (size of the observable universe is constant) avoids the whole question of time complexity. To actually measure the time complexity of the algorithm, you need to consider inputs of different sizes. You could run exactly the same algorithm in a different universe (that is why it's called "universal" after all) and you'd get a different running time. The time complexity is then the relationship between the two running times and the universe sizes.
