Parallel Solutions

Program Maximum4
   declare $t$: integer
   initially $t$=N
   assign
      <|| $i$ : 0 ::
         A[$i$] := max(A[2*$i$], A[2*$i$+1])>
      ||$t$ := $t$/2
end {Maximum4}

• Let $A0$ be the initial value of $A$.
• invariant <max $i$: 0 :: $A[i]$>= <max $i$: 0 :: $A0[i]$>
• $t=1$ $=>$ $A[0]$ = <max $i$: 0 :: $A0[i]$>