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!

  • $\begingroup$ What does Shuffle([a]) (one element) do? $\endgroup$
    – ttnick
    Jan 19 at 11:09
  • 2
    $\begingroup$ Why did you vandalize your own post? $\endgroup$ Jan 22 at 21:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – Discrete lizard
    Jan 22 at 21:49
  • $\begingroup$ 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. $\endgroup$ 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)$$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.