Analyzing the Runtime of Shuffling Algorithm

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!

• What does Shuffle([a]) (one element) do? – ttnick Jan 19 at 11:09
• Why did you vandalize your own post? – Dannyu NDos Jan 22 at 21:19
• 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. – Inuyasha Yagami Jan 24 at 7:20

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)$$.