An assignment question asks me to find the complexity of a [tail] recursive algorithm, copied below. While I understand all the complexity specifics, for example that the while loop's complexity is $n-1$ and the complexity of setting $j$ to $0$ is 1, I don't understand how I could trace the code recursively, that is within itsel - it's too hard to keep track of.

What I tried doing, is turning the algorithm into an iterative one, by simply putting all the code into a big while loop and thus avoiding the recursive call. But I'm not sure if this affects the complexity of the original algorithm.

Algorithm MyAlgorithm(A, n) 
   Input: Array of integer containing n elements 
   Output: Possibly modified Array A
     done ← true 
     j ← 0
     while j ≤ n - 2 do {
       if A[j] > A[j + 1] then {
       swap(A[j], A[j + 1])
       done:= false
     j ← j + 1
     end while
     j ← n - 1
     while j ≥ 1 do
       if A[j] < A[j - 1] then
       swap(A[j - 1], A[j])
       done:= false
    j ← j - 1
    end while
    if ¬ done
       MyAlgorithm(A, n)
      return A
  • $\begingroup$ I wrote the code in Java and tried both options (recursive and iterative) and they are indeed identical. However I'm still hoping to find out if there's a way to determine complexity exclusively using recursive method. $\endgroup$ – CodyBugstein Jan 31 '13 at 17:18

You have to analyze the circumstances in which your algorithm makes a recursive call. That is, when is not done true? Well, your it's true whenever your algorithm is required to make a swap in one of its passes over the array (one of the while loops). To analyze the total worst case running time, determine the maximum number of recursive calls, and add up the total work in each of these calls. In some recursive algorithms, the amount of work in each recursive call might be different. Is that the case in your algorithm?

  • $\begingroup$ Exactly, there's no clear way to determine how many recursive calls it will make. I suppose it's roughly n (n being the size of the array, the worst being an array in exactly the wrong order). But how do I quantify that as a value? $\endgroup$ – CodyBugstein Feb 1 '13 at 2:58
  • $\begingroup$ The problem is a bit more interesting than the usual "find the complexity" problem, because you need to actually analyse what the algorithm does and what effect it has, instead of just counting loop iterations. The "roughly n" is just a guess; a one line change in the algorithm makes it run forever. The hint would be: After the first run through MyAlgorithm, where would we find the largest and the smallest element of the array? $\endgroup$ – gnasher729 May 6 '14 at 16:33

Hint 1: This algorithm is similar to bubble sort. It sorts the array in ascending order.

Hint 2: Try to work out what the series of swaps do when taken to completion. For example, what happens when the two while loops are run on the following array: $\{4, 2, 5, 6, 1, 3\}$. After the first while loop, is some part of the array sorted? What after the second loop? What after the function is recursively called again?

Hint 3: Worst case performance, as you guessed, would be when the array is reverse sorted - due to maximum number of swap operations.

I think these are substantial hints for an assignment problem, and you should be able to work it out from here.


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.