Spacing too large with exponents and big Oh

There are a number of ways to address spacing issues. In the first example you give, reproduced in the first gather* line in the code below, both the right large parenthesis and the exponent n indeed seem to be spaced too loosely.

Inserting a "negative thinspace", \!, before each of these two items (line 2) does eliminate the earlier looseness. Unfortunately, the overall expression now looks a bit cramped. In my view, the real culprits for making the expression in line 1 look unsatisfactory are (i) the near-collision between the opening (left) parenthesis and the subscript term below the product symbol and (ii) parentheses that are too tall relative to what they contain; see pp. 148-9 of the TeXbook for an explanation of this second point. In line 3 below, I therefore (a) insert a positive thinspace, \, after the opening parenthesis and (b) use \biggl and \biggr parentheses, as they are slightly smaller (and also a tiny bit less wide!) than those produced by \left( and \right). I think the result now looks both balanced and neither too loose nor too tight. :-)

The second example you provide is affected by the automatic additional spacing that's inserted when TeX creates \left- and \right parentheses. Switching to \biggl and \biggr parentheses, as in line 4 below, eliminates this excess space. If you do not wish to give up the convenience of automatic sizing of parentheses generated by \left-\right pairs, you could instead insert a negative thinspace, \!, between the O and the \left(.

\documentclass[a4paper,11pt]{article}
\usepackage{amsmath}
\begin{document}
\noindent
\begin {gather*}
\intertext{Original}
 \left( \prod_{i=1}^m X_i \right)^n  \\       %% "line 1"
\intertext{less space on \emph{right}:}
 \left( \prod_{i=1}^m X_i \!\right)^{\!n} \\  %% "line 2"
\intertext{more space on \emph{left}, biggl-biggr parens:}
 \biggl(\,\prod_{i=1}^m X_i\biggr)^n \\       %% "line 3"
\intertext{Left-right vs.\ biggl-biggr parentheses}
 O\left(\frac{1}{n}\right) \qquad O\biggl(\frac{1}{n}\biggr)  %% "line 4"
\end{gather*}
\end{document}

use it this way:

\documentclass{article}

\begin{document}
\[ \left( \prod_{i=1}^m X_i \right)^{\mkern-5mu n} \]
\[ O{\left(\frac{1}{n}\right)} \]
\end{document}

with {...} you do not get the delimiterspace. The exponent is correct but you can use \mkern to get it nearer to the parenthesis