We assume that the numpy module of Python has been imported using the instruction \texttt{import numpy as np}. This thus gives access to the following functions:
\texttt{np.identity( n )} creates $I _ { n }$, the identity matrix of order n;
\texttt{A.shape} gives, in the form of a tuple, the size of array A, for example \texttt{np.identity(5).shape} $\rightarrow ( 5,5 )$;
\texttt{np.dot(A, B)} computes the matrix product of A and B if A and B are two-dimensional arrays compatible with matrix multiplication.
The naive algorithm for computing $B^k$ uses: $$\left\{ \begin{array} { l } B ^ { 0 } = I _ { n } \\ B ^ { k } = B B ^ { k - 1 } \quad \forall k \geqslant 1 \end{array} \right.$$ The fast exponentiation algorithm uses: $$\begin{cases} B ^ { 0 } = I _ { n } & \\ B ^ { k } = \left( B ^ { 2 } \right) ^ { \frac { k } { 2 } } & \text { if } k \text { is even } \\ B ^ { k } = B \left( B ^ { 2 } \right) ^ { \frac { k - 1 } { 2 } } & \text { if } k \text { is odd.} \end{cases}$$ We assume that $k \geqslant 2$ and we denote by $p$ the unique integer such that $2 ^ { p } \leqslant k < 2 ^ { p + 1 }$. For each of the calls \texttt{puissance1(B, k)} and \texttt{puissance2(B, k)}, compute the number of calls to the function \texttt{np.dot}, in the worst case and in the best case.
We assume that the numpy module of Python has been imported using the instruction \texttt{import numpy as np}. This thus gives access to the following functions:
\begin{itemize}
\item \texttt{np.identity( n )} creates $I _ { n }$, the identity matrix of order n;
\item \texttt{A.shape} gives, in the form of a tuple, the size of array A, for example \texttt{np.identity(5).shape} $\rightarrow ( 5,5 )$;
\item \texttt{np.dot(A, B)} computes the matrix product of A and B if A and B are two-dimensional arrays compatible with matrix multiplication.
\end{itemize}
The naive algorithm for computing $B^k$ uses:
$$\left\{ \begin{array} { l } B ^ { 0 } = I _ { n } \\ B ^ { k } = B B ^ { k - 1 } \quad \forall k \geqslant 1 \end{array} \right.$$
The fast exponentiation algorithm uses:
$$\begin{cases} B ^ { 0 } = I _ { n } & \\ B ^ { k } = \left( B ^ { 2 } \right) ^ { \frac { k } { 2 } } & \text { if } k \text { is even } \\ B ^ { k } = B \left( B ^ { 2 } \right) ^ { \frac { k - 1 } { 2 } } & \text { if } k \text { is odd.} \end{cases}$$
We assume that $k \geqslant 2$ and we denote by $p$ the unique integer such that $2 ^ { p } \leqslant k < 2 ^ { p + 1 }$. For each of the calls \texttt{puissance1(B, k)} and \texttt{puissance2(B, k)}, compute the number of calls to the function \texttt{np.dot}, in the worst case and in the best case.