The complexity of the problem as stated is worst case O(n^3) in the magnitude of the greatest value a[i]. The reason being that it is a simple sum, as stated, of square roots. The square root operation is O(n^2) in the number of bits, which has a 3.xxx:1 relation to the magnitude of each a[i]. Either the problem is mistated or it has not been significant enough for anyone to waste time on stating the obvious.
login/create account
Drupal
CSI of Charles University
Complexity
The complexity of the problem as stated is worst case O(n^3) in the magnitude of the greatest value a[i]. The reason being that it is a simple sum, as stated, of square roots. The square root operation is O(n^2) in the number of bits, which has a 3.xxx:1 relation to the magnitude of each a[i]. Either the problem is mistated or it has not been significant enough for anyone to waste time on stating the obvious.