3
$\begingroup$

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)?

$\endgroup$
  • 2
    $\begingroup$ One question per question, please. Your second question is an entirely separate question and should have been posted separately; you should ask only one question per question. Also, asking whether recursive algorithms are better is far too broad of a question for this site, as the only answer will be "it depends". $\endgroup$ – D.W. Apr 11 '16 at 20:59
  • $\begingroup$ Since you always simulate recursion using explicit stacks, how can recursion "admit better complexity"? $\endgroup$ – Raphael Apr 11 '16 at 21:11
  • 1
    $\begingroup$ Recursive algorithms don't necessarily take up more space; tail-recursive algorithms in principle can run in constant space. $\endgroup$ – jamesdlin Apr 11 '16 at 22:10
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
7
$\begingroup$

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?.

| cite | improve this answer | |
$\endgroup$

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.