Fair point! It's interesting to figure out what the complexity must be. There are certainly n additions to perform, and the numbers being added on the k'th ste

Fair point! It's interesting to figure out what the complexity must be. There are certainly n additions to perform, and the numbers being added on the k'th step are of size O(phi^k) which will take O(log(phi^k)) = O(k log(phi)) to add. Therefore the total running time is 1 + 2 + ... + n = O(n^2) so the theory predicts quadratic, not linear time. I wonder if this is borne out by numerical experiments.