On the complexity of computing the Lq norm

Abstract We study the complexity of computing the norm ‖ f ‖ L q ( Q ) , where f is from the unit ball of a Sobolev space W p r ( Q ) and Q = [ 0 , 1 ] d is the unit cube. The deterministic case is a consequence of a general result by Wasilkowski. We consider the randomized setting with standard information and determine the order of the randomized n th minimal error. Furthermore, we discuss problems related to the arithmetic cost of the proposed algorithms and present modifications of nearly optimal arithmetic cost in the one-dimensional case.