Improvement 0 Maintain the sum and sum of squares of the input numbers. ■ sum =0;sos =0 for i=1 ton-2 sumsum xi SOs Sos+x n(n+1) n(n+1)(2n+1) ■a三 -sum,b= 9 OS 2 6 ■ solve equations x+y=a,x2+y2=b. o return (x,y) 11
Improvement ◼ Maintain the sum and sum of squares of the input numbers. ◼ 𝑠𝑢𝑚 = 0; 𝑠𝑜𝑠 = 0 ◼ for 𝑖 = 1 to 𝑛 − 2 𝑠𝑢𝑚 = 𝑠𝑢𝑚 + 𝑥𝑖 𝑠𝑜𝑠 = 𝑠𝑜𝑠 + 𝑥𝑖 2 ◼ 𝑎 = 𝑛 𝑛+1 2 − 𝑠𝑢𝑚, 𝑏 = 𝑛 𝑛+1 2𝑛+1 6 − 𝑠𝑜𝑠 ◼ solve equations 𝑥 + 𝑦 = 𝑎, 𝑥 2 + 𝑦 2 = 𝑏. ◼ return (𝑥, 𝑦) 11
Space complexity sos is at most n(n+1)(2n+1) during the 6 algorithm. Thus it takes at most logz n(n+1)(2n+1) 6 0(log2 n)bits to write it down. Space complexity:0(log2n). 12
Space complexity ◼ 𝑠𝑜𝑠 is at most 𝑛 𝑛+1 2𝑛+1 6 during the algorithm. ◼ Thus it takes at most log2 𝑛 𝑛+1 2𝑛+1 6 = 𝑂 log2 𝑛 bits to write it down. ◼ Space complexity:𝑂 log2 𝑛 . 12