Analyzing the Runtime of Shuffling Algorithm

Question

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.

Algorithm 1:

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

Algorithm 2:

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!

• ttnick: What does Shuffle([a]) (one element) do?
• Dannyu NDos: Why did you vandalize your own post?
• Discrete lizard: Please do not delete your question once you have received a helpful reply. Instead, consider accepting an answer that has been useful. Be aware that people are answering your question not only to help you, but also to help future visitors with similar questions.
• Inuyasha Yagami: Please do let a previous answerer know whenever you make a significant logical change to your question. Otherwise, other folks would learn the wrong concepts and might even downvote the previous answer.

Answer 1

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) &= 4 \cdot T(n/2) + O(n^{2}) \\ &= 4 \cdot (4 \cdot T(n/4) + O(n^{2}/4)) + O(n^{2}) \\ &= 4^{3} \cdot T(n/8) + 4^{2} \cdot O(n/4^{2}) + 4 \cdot O(n^{2}/4) + O(n^{2}) \\ & \quad ,円 \textrm{... on further expansion we get the following relation} \\ &= 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)$$.