Analyzing the Runtime of Shuffling Algorithm
You are right about the running time of the second algorithm, i.e., Shuffle1$(A)$. Its running time is indeed $O(n^{3} \cdot m^2)$.
To analyze the running time of the first algorithm, i.e., Shuffle$(A)$, you can formulate the recurrence relation as follows:
$$T(n) = 4 \cdot T(n/2) + O(n^2)$$
Note that, Random(10) takes time $O(10^2) = O(1)$.
You can indeed solve this recurrence using the Master Theorem. The theorem gives $T(n) = O(n^{2} \log n)$ by applying Case $2$ of the theorem.

You can also solve the recurrence by the expansion method as described below:
$$
\begin{align}
T(n) &amp;= 4 \cdot T(n/2) + O(n^{2}) \\
&amp;= 4 \cdot (4 \cdot T(n/4) + O(n^{2}/4)) + O(n^{2}) \\
&amp;= 4^{3} \cdot T(n/8) + 4^{2} \cdot O(n/4^{2}) + 4 \cdot O(n^{2}/4) + O(n^{2}) \\
&amp; \quad \, \textrm{... on further expansion we get the following relation} \\
&amp;= 4^{t} \cdot T(n/2^{t}) + \sum_{i = 0}^{t} 4^{i} \cdot O(n^{2}/4^{i}) \\
\end{align}
$$
When $t = \log n$, the value $T(n/2^{t})$ becomes $T(1)$. I am assuming that $T(1) = 1$ for the base case of your algorithm. (ttnick is asking the same question in the comment section also). Based on this assumption, we get the following relation:
$$T(n) = (4)^{\log n} \cdot 1 + \sum_{i = 1}^{\log n} O(n^{2}) = n^{2} + \sum_{i = 1}^{\log n} O(n^{2}) = O(n^2 \log n)$$.