## 4 Approaches to the reconstruction problem from protein contact maps
### Computational complexity of the methods  
The analysis of the computational complexity of the heuristic algorithms presented here is difficult because all such algorithms are iterative and there is no simple way to determine good upper bounds to the speed of convergence, which typically depends of how well the initial solution is chosen. Anyway, it is still possible to provide an accurate analysis of the cost needed to generate an initial solution and to execute an iterative step.  
The initial solution for the methods described in Section 4.1. is randomly chosen then it costs \(O(N)\) (there are just \(N\) coordinates which describe the structure). Assume to use a gradient descent method to minimize the energy cost function. The cost of an iterative step for the first ([PERSON] et al.) and the second ([PERSON] and [PERSON]) methods can be upper bounded by the time needed to compute the partial derivatives of equations (2) and (4), respectively. Since in both cases the summation term contains exactly \(N^{2}+(N-1)\) distances, the computational complexity of an iterative step for both algorithms is upper bounded by \(O(N^{2})\).  
In the simulated annealing approaches of Section 4.2., the cost of the growth phase is dominated by the cost to compute the score for every newly added coordinate to the growing chain. Since for every newly added \(i\)-th coordinate we have to compute the score by considering the previous \((i-1)\) coordinates (see, for example, equation (6)), the total cost is on the order of \(N(N+1)/2\). Then growing the chain costs \(O(N^{2})\). In the adaptation phase the cost of the displacement is bounded by the time needed to compute the energy functions (7) for the first method ([PERSON] et al.) and (8) for the second method ([PERSON] et al.). Recall that for the second method, it can happen to displace a whole alpha helix. Then the cost of a displacement is \(O(N)\) for the first method and \(O(dN)\) for the second method, where \(d\) is the length of the largest alpha helix. If we assume that an iterative step of these methods consists of the displacement of all coordinates then for both algorithms an iterative step costs \(O(N^{2})\) in the worst case.  
In the distance geometry based algorithm of Section 4.3. ([PERSON] et al.), the cost to generate an initial solution is bounded by the cost of the Embed algorithm which is \(O(N^{3})\). In fact, in the worst case, the contact map contains no independent components and the Embed algorithm runs on the entire map. During the iterative correction phase (both in the second and third phase) the two more time-consuming operations are the calculation of the radius of mobility (9) and of the pseudo-force (10). The cost to correct the position of one coordinate is then \(O(N)\). In the same way, the cost to perturbate one coordinate is \(O(N)\) which implies that the total cost of a single displacement is \(O(N)\). As in the previous case, if one iteration step terminates when all coordinates have been eventually displaced, then an iterative step costs \(O(N^{2})\) in the worst case.  
In conclusion, the iterative step is quadratic in the dimension of the input for all reviewed algorithms. The speed of convergence is very likely to depend on the quality of the initial solution. In this sense, although more costly, the choice to build an initial solution by means of a growing process or by using a distance geometry approach can be more effective than the random approach. The only reports about the running time of the algorithms on modern processors refer to the two more recent methods (i.e. [PERSON] et al, and [PERSON] et al.). In both cases the authors report their methods to have total running time on the order of a few seconds for a medium-size protein.