I have stumbled upon an equation (http://i.stack.imgur.com/hv64E.png), where the probability of an occupancy grid map cell is calculated. My teacher insists that it's possible to approximate the algorithmic complexity of this long equation, but I'm not so sure.

The description of the factors used in this equation are described here on page 11 (item 26). With keeping in mind that this calculates occupancy probabilities of a 2 dimensional array from sensor measurements, is it really possible to approximate the algorithmic complexity of actually calculating occupancy with this equation in BigO by just taking a look at it and not delving much deeper into the details?

  • 1
    $\begingroup$ Unless I'm mistaken all the variables in the equations are just numbers, right? So there is only the sum that you need more than O(1) to evaluate... $\endgroup$
    – cube
    Jan 23 '15 at 18:25
  • $\begingroup$ They are numbers once they're calculated, but finding them might require more, possibly complex calculations, and this is the reason why I'm skeptical about the possibility of evaluating the algorithmic complexity so easily. $\endgroup$ Jan 23 '15 at 20:54

The referenced picture of an equation is this: picture of equation and in latex it is: \begin{equation}\tag{26} p(z_t|m,c_t) = \frac{1}{\sqrt{2\pi\sigma^2}} e^{-\frac{1}{2}\left\{ c_{t,*}\log{\frac{z^2_{max}}{2\pi\sigma^2}} + \sum_{k=1}^{K_t}c_{t,k}\frac{(z_t-d_{t,k})^2}{\sigma^2} + c_{t,0}\frac{(z_t-z_{max})^2}{\sigma^2} \right\}} \end{equation}

For a single $p(z_t|m,c_t)$ calculation, the algorithmic complexity of computation is O($K_t$) if it is the case that $K_t$ values of $c_{t,k}$ need to be examined, or is O(1) if the index of the non-zero $c_{t,k}$ or $c_{t,*}$ value that is non-zero is given. (The referenced paper at roboticsclub.org stiputates that only one of the $K_t+2$ possible $c_{t,k}$ values is non-zero.)

To see this, note that every value used in the equation is a constant, or a parameter specified or given, or an index of summation. Each of the values used requires time O(1) to obtain. The summation takes O(1) or O($K_t$) time to compute, as noted above. The logarithms, squares and square roots, and all the other arithmetic operations take O(1) time (assuming use of fixed-length operands and arithmetic, eg double-precision values and operations). A fixed-length sequence of O(1) operations takes O(1) time.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.