Time complexity (Big-O notation) of Posterior Probability Calculation
I got a basic idea of Big-O notation from Big-O notation's definition.
In my problem, a 2-D surface is divided into uniform M grids. Each grid (m) is assigned with a posterior probability based on A features.
The posterior probability of m grid is calculated as follows:
and the marginal likelihood is given as:
Here, A features are independent of each other and sigma and mean symbol represent the standard deviation and mean value of each a feature at each grid. I need to calculate the Posterior probability of all M grids.
What will be the time complexity of the above operation in terms of Big-O notation?
My guess is O(M) or O(M+A). Am I correct? I'm expecting an authenticate answer to present at the formal forum.
Also, what will be the time complexity if M grids are divided into T clusters where every cluster has Q grids (Q << M) (calculating Posterior Probability only on Q grids out of M grids) ?
Thank you very much.
Discrete sum and product
can be understood as loops. If you are happy with floating point approximation most other operators are typically O(1), conditional probability looks like a function call. Just inject constants and variables in your equation and you'll get the expected Big-O, the details of formula are irrelevant. Also be aware that these "loops" can often be simplified using mathematical properties.
If the result is not obvious, please convert your above mathematical formula in actual programming code in a programming language. Computer Science Big-O is never about a formula but about an actual translation of it in programming steps, depending on the implementation the same formula can lead to very different execution complexities. As different as adding integers by actually performing sum O(n) or applying Gauss formula O(1) for instance.
By the way why are you doing a discrete sum on a discrete domaine N ? Shouldn't it be M ?
- Time complexity of recursive permutation printer
- Why is accessing any single element in an array done in constant time ( O(1) )?
- Understanding Time complexity calculation for Dijkstra Algorithm
- consecutive pairs divisible by 3
- Difference between Big-O and Little-O Notation
- How do I check if an array includes a value in JavaScript?
- Fastest way to find the smallest possible sum of the absolute differences of pairs within a single array?
- Finding maximum groups in less time complexity
- Can we get a better complexity than O(n) for cumulative sum while using multithreading?
- Given tasks and programmers solve the tasks in less time
- How can I remove all items in a HashMap where key value is greater than a defined value
- Worst scenario for shell sort: Θ(N^3/2) or O((NlogN)^2)?
- Deriving a mathematical formulation for my recursive solution?
- What is a plain English explanation of "Big O" notation?
- What is a quick way to count the number of pairs in a list where a XOR b is greater than a AND b?
- Why is O(n) better than O( nlog(n) )?
- Deriving O(N*log(N)) for Comparison Sort, question on one particular step in wikipedia's derivation
- Function to find largest area of a rectangle possible (NOT neccessarily axis parallel) from a list of points
- Is My Time Complexity Analysis for Finding Universal Words O(m * k^2 + n*k) correct?
- time complexity exercise (pseudo code)
- Improve computational time and memory usage of the calculation of a large Matrix that has four loops
- Dynamic array first element remove complexity
- Does the choice of compiler and language affect Time Complexity?
- What would cause an algorithm to have O(log log n) complexity?
- Time complexity of Boost Graph function vertex() on adjacency_list
- Why when I use .size() to compute the length of array in the Conditional Determination of for Loop Structures will time out in leetcode?
- How can `HashSet<T>.Contains` be O(1) with this implementation?
- Space and time complexity of flattening a nested list of arbitrary depth
- Isn't every algorithm technically ω(0)?
- Time complexity of nested for-loop