Complexity of Oscillatory Integrals on the Real Line

We analyze univariate oscillatory integrals defined on the real line for functions from the standard Sobolev space $H^s(\mathbb{R})$ and from the space $C^s(\mathbb{R})$ with an arbitrary integer $s\ge 1$. We find tight upper and lower bounds for the worst case error of optimal algorithms that use $n$ function values. More specifically, we study integrals of the form $$I_k^{\rho }(f)={\int }_{\mathbb{R}}f(x)e^{-ikx}\rho (x)\mathrm{d}xforf\in H^s(\mathbb{R})orf\in C^s(\mathbb{R})$$ with $k\in \mathbb{R}$ and a smooth density function $\rho$ such as $\rho (x)=\frac{1}{\sqrt{2\pi }}\exp (-x^2\mathrm{/}2)$. The optimal error bounds are $\mathrm{\Theta }((n+\max (1,\mathrm{\mid }k\mathrm{\mid }){)}^{-s})$ with the factors in the $\mathrm{\Theta }$ notation dependent only on $s$ and $\rho$.