Consider the following algorithm that computes the Hamming distance between two arrays

$($the number of indices i where A$[$i$]=$ B$[$i$]).$

Algorithm $1$ Hamming$($A$,$ B$)$

$1$: Let length$($A$)=$ length$($B$)=$ n

$2$: if n $=1$ then

$3$: if A$[0]=$ B$[0]$ then

$4$: Return $0$

$5$: else

$6$: Return $1$

$7$: end if

$8$: else

$9$: Return Hamming$($A$[0$ : n

$31],$ B$[0$ : n

$31])+$ Hamming$($A$[$ n

$3$ : n $1],$ B$[$ n

$3$ : n $1])$

$10$: end if

$1.$ Write the running time of Algorithm $1$ as a recurrence relation. Assume that the

array initialization can all be done in constant time using pointers.

$2.$ Describe the running time of this function using big$-$O notation