A friend majoring in finance wants to implement an algorithm for computing the

prefix variance of a sequence dataset of $n$ real$-$valued numbers $a_0,a_1,$dots,$a_{n-1},$ defined as the

sequence of $n$ real$-$valued numbers widehat$({)}_0^2,$widehat$({)}_1^2,$dots,widehat$({)}_{n-1}^2$ such that $t=0,1,$dots,$n-1,$

widehat$({)}_t^2=\frac{1}{t+1}{\displaystyle \underset{i=0}{\overset{t}{}}}(a_i-(\frac{1}{t+1}{\displaystyle \underset{j=0}{\overset{t}{}}}{a}_j){)}^2.$

Our friend, having found the following two algorithms, PREFIXVARIANCE$1$ and PREFIXVARIANCE$2,$

that perform the task correctly but not knowing which one to implement, is asking for your

recommendation. Both algorithms take as input an $n-$element array A such that each element

$A[i]=a_i$ for all $i=0,1,$dots,$n-1,$ and output an $n-$element array $B$ such that each element

$B[i]=$widehat$({)}_i^2$ for all $i=0,1,$dots,$n-1$ with the corresponding prefix variance evaluation of the

sequence in $A.$

Algorithm $1$ PREFIXVARIANCE$1(A)$

Blarr new array of $n$ numbers

for tlarr$0$ to $n-1$ do

vlarr$0$

for ilarr$0$ to $t$ do

zlarr$0$

for jlarr$0$ to $t$ do

zlarrz$+A[j]$

zlarr$\frac{z}{t+1}$

dlarrA$[i]-z$

vlarrv$+d**d$

$B[t]larr\frac{v}{t+1}$

return $B$

Algorithm $2$ PREFIXVARIANCE$2(A)$

Blarr new array of $n$ numbers

for tlarr$0$ to $n-1$ do

zlarr$0$

for ilarr$0$ to $t$ do

zlarrz$+A[i]$

zlarr$\frac{z}{t+1}$

vlarr$0$

for ilarr$0$ to $t$ do

dlarrA$[i]-z$

vlarrv$+d**d$

$B[t]larr\frac{v}{t+1}$

return $B$

$1)$ Give time and space characterization using big$-$oh for prefixvariance$1$

$2)$ Give time and space characterization using big $-$oh for prefixvariance $2$

$3)$ which one do you reccomend based on this and why