I have the following integral:
$$p(x) = \int p(\pmb{\mu})\prod_{i=1}^n\sum_{c_i}p(c_i)p(x_i|c_i,\pmb{\mu})d\pmb{\mu}$$ $\pmb{\mu} \in \mathbf{R}^K$ . The time complexity to numerically evaluate this integral is $\mathcal{O}(K^n)$ but I am not sure how this number is obtained?
I was trying to understand the same and arrived here haha. I think a good way to see it, is to decompose the integral.
$$ p(x) = \int p(\mu)\prod^{n}_{i=1}(f_{i,\mu_1}+f_{i,\mu_2}+..+f_{i,\mu_k})$$
Imagine $n=1$, In this case, to numerically evaluate the integral we have $K$ terms and the complexity is $O(K)$.
Now with $n=2$ we have
$$ p(x) = \int p(\mu)(f_{1,\mu_1}+f_{1,\mu_2}+..+f_{1,\mu_k})(f_{2,\mu_1}+f_{2,\mu_2}+..+f_{2,\mu_k}) $$
Then,for each new sample that you add, you are multiplying the number of terms by $K$ and the complexity of $n$ number of samples is $O(K^n)$.