The following is psuedocode used to shuffle the contents of an array $A$ of length $n$. As a subroutine for shuffle, there is a call to Random$(m)$ which takes $O(m^2)$ time for an input $m$. Determine the runtime of the following algorithms.
function Shuffle(A) Split A into two equal pieces A, and B (this takes constant time) A = Shuffle(A) B = Shuffle(B) for i = 0 to len(A)/2 − 1: for j = 0 to i − 1 do: B[j] = B[j] − A[i] + Random(10) A[i] = A[j] − B[i] + Random(10) B = Shuffle(B) A = Shuffle(A) Combine A = A + B (this takes constant time) return A
function Shuffle1(A) for i = 0 to len(A) − 1: for j = 0 to i − 1: for k = 0 to j − 1: A[k] = A[k] + A[j] + A[i] + Random(m) return A
After a good amount of work, I believe that the runtime for Shuffle1$(A)$ to be $O(n^3 \cdot m^2)$ as there are three nested loops. In the innermost loop, the algorithm does the constant time array access and $O(m^2)$ work done. But, I am not quite sure. I am having difficulty tackling the runtime of Shuffle(A). Should I be using the Master Theorem in any way? Any advice and help would be greatly appreciated!