It is known that for \(m\)  nodes, the computational complexity of PRM is \(O(m\log m)\)  [1]}. First let us consider the case of belief space planning over the PRM graph, without computing the collision probabilities. Finding a trajectory to the goal requires performing Bayesian (EKF) update operations. This basically involves performing matrix operations— matrix multiplication and inversion of matrices. For a state of dimension \(n\) , the covariance matrix is of dimension \(O(n^2)\) . Therefore, each step of the Bayesian update has a complexity of \(O(n^3)\) . If \(T\)  denotes the number of time steps in the trajectory, then the overall computational complexity is \(O(n^3T)\) . Let us now analyze the complexity of collision probability computation. From (REF ) we see that for each iteration, the truncation error varies with \((y/2\rho )\) . Therefore, to achieve \(E(N) \le \delta \) , for an \(\epsilon -\) safe configuration, \(k = O\left(\log \frac{\delta \rho }{y(1-\epsilon )}\right)\)  iterations are required. We note that for each obstacle, the runtime is increased by this factor.
