How is the complexity of recursive algorithms calculated and do they admit better complexity than non-recursive algorithms?

Question

How are asymptotical time complexities calculated for recursive algorithms?

Recursive algorithms call themselves and therefore take up more space compared to non-recursive algorithms. But are they better taking time complexity into account? If they are better than non-recursive algorithms, then how are they better and why (not)?

Answer 1

When the design of an algorithm is ready, one can evaluate its running time. If one wishes to implement the algorithm, (s)he can do so recursively or iteratively. It's just an implementation detail, it won't affect asymptotical running time.

As an example, consider the problem of sorting an array of size $n$.

There are a lot of algorithms to solve this problem with a lot of different time complexities. Two examples are:

• Merge Sort, which runs in $O(n\times log(n))$;
• Insertion Sort, which runs in $O(n^2)$.

Both algorithms can either be implemented using a recursive approach or an iterative approach. It will not affect their asymptotical running time.

Assume we're given a recursive version of Merge Sort and we wish to evaluate it's running time.

func mergesort( var a as array )
     if ( n == 1 ) return a

     var l1 as array = a[0] ... a[n/2]
     var l2 as array = a[n/2+1] ... a[n]

     l1 = mergesort( l1 )
     l2 = mergesort( l2 )

     return merge( l1, l2 )
end func

This pseudocode takes an array as input, divides the given array in half, recursively calls mergesort on both halves and then merges both halves. The merging process looks like

func merge( var a as array, var b as array )
     var c as array

     while ( a and b have elements )
          if ( a[0] > b[0] )
               add b[0] to the end of c
               remove b[0] from b
          else
               add a[0] to the end of c
               remove a[0] from a
     while ( a has elements )
          add a[0] to the end of c
          remove a[0] from a
     while ( b has elements )
          add b[0] to the end of c
          remove b[0] from b
     return c
end func

The (iterative) merge function takes two arrays as input. It will compare the first element of both arrays. The biggest element is added to the last not-yet-filled-in slot of a new array $c$. Then, the biggest element is removed from its array. This is repeated until both given arrays are empty, the now fully filled list $c$, which is sorted, will be returned.

One can calculate the running time of merge sort by solving its recurrence:

$T(n) = 2T(\frac{n}{2}) + O(n)$.

The running time of any recursive algorithm can be represented by a similar equation above.

$T(n)$ represents our asymptotic running time. The term $2T(\frac{n}{2})$ is there because in our algorithm we recursively call the same algorithm twice and pass it an array with input size which is half of our original input size. The term $O(n)$ is there because we call the algorithm merge after, which runs in $O(n)$ (do you see why?).

To solve the recurrence, we can apply the master theorem. Case two applies here (do you see why?), so we can conclude that merge sort runs in $T(n) = \Theta(n \times log(n))$.

I will not discuss an iterative implementation of merge sort here. But if you would look it up and evaluate its running time; you would see it runs in the same running time.

To summarize, the design/general idea of an algorithm defines its running time. Recursive/Iterative versions of it are just an implementation detail.

I sense you are also wondering what the advantage/disadvantage of a recursive algorithm is over its iterative sibling since they're equivalent in running time anyway.

The disadvantage you mention (it takes more space on the stack) is generally a very small one and is only a significant problem in a few circumstances. The advantage of recursive algorithms could be that their implementation results in much cleaner, less and more readible code. Merge sort is a nice example to express this advantage.

Answer 2

Typically, by writing a recurrence relation for the running time and then solving the recurrence relation. See How to come up with the runtime of algorithms? and Solving or approximating recurrence relations for sequences of numbers. You might also want to read your friendly textbook and Is there a system behind the magic of algorithm analysis?.