I have to solve a nonlinear (trigonometric) equation (that always has only one solution) $$f(x)=0$$ where function $f: D \subset \mathbb{R} \to \mathbb{R}$ is strictly increasing. I used the MATLAB function fsolve with the "trust-region-dogleg" method to solve the equation and the result is fine.
I would like to know the computational complexity of the algorithm used by MATLAB (i.e. trust-region method) in my case. Can I say that the CPU's computational time for solving such problem is the complexity of the algorithm?
I very much appreciate any answer or suggestion!
Best Answer
You can have a grasp on the required time by comparing execution times under different conditions.
For instance, what happens if $D$ was twice the dimension, or you required twice the precision?
Let's put a simple example: adding two binary numbers $a,b$ of length $k$ requires $\mathbb{O}(k)$ operations to be computed. But $k$ is roughly $\log_2{a}$, so you can say the computation is $\mathbb{O}(\max{(\log_2{a},\log_2{b})})$
Note that, if we work with $a+1$ and $b+1$ rather than $a$ and $b$, we don't expect to need any extra opreations, except in the case one of them happens to be $111....111$ (or $999...999$ if we work in decimal)
If we need numbers with an extra digit (like $2a$ and $2b$), we will need one more operation. If we need numbers twice as long (like $a^2$ and $b^2$) we will need twice as many operations. Note that this fits well into the log-order complexity, since:
$$\log{(x+1)} \cong \log{(x)}$$ $$\log{(2x)} \cong 1+ \log{(x)}$$ $$\log{x^2} = 2 \log{(x)}$$
This types of relationships is what we usually check to find computationanl complexity in practice. Note that time is to some extent proportional to the number of basic operations (bit-additions), so we can use time as a "proxy" and work with it instead. That's why I suggest to check what happens when you have one more variable or twice as many variables in order to grasp the relationship between execution time and number of variables.
EDIT: Now that we know $D \subset \mathbb{R}$ the number of variables comparison does not apply. But you may want to use the complexity of $f$ (for example, adding a few degrees is $f$ is a polynomial), or the precision of the solution