2
$\begingroup$
"The designer of an algorithm needs to balance between space complexity and time
complexity." - Comment on the validity of the statement in the context of recursive
algorithms.

This is a question from my university's previous paper. But i couldn't find a decent answer. Actually i am confused about how can a developer minimize the time-complexity for any recursive function. I get that if there is a tail-recursion then space complexity can be minimized. But can't get the idea of time-complexity.

$\endgroup$
  • 3
    $\begingroup$ I don't think you quite understand the question. The space-time tradeoff is about decreasing space or time at the cost of the other ("balance between" points to this being what the question is talking about). So I don't think tail-recursion classifies - I believe it decreases both. $\endgroup$ – Dukeling Jul 3 '13 at 11:55
5
$\begingroup$

One thing comes in mind is memoization. Simple well studied problem for this is Fibonacci numbers, simple recursion is as follow:

fib(int n)
{
  if (n < 3)
    return 1;

  return fib(n-1) + fib(n-2);
}

But with memoization, we can use an auxiliary array to get rid of extra calls:

f[1]=f[2] = 1;
fib(int n)
{
  if (n < 3)
    return 1;

  if (f[n] == 0)
     f[n] = fib(n-1) + fib(n-2);

  return f[n];
}

This simple change, reduces the time from $\Theta(\phi^n)$ to $\Theta(n)$.

The memoization technique sometimes uses more memory, but very faster in time, and one of a tradeoffs that software developer should be care about it is this.

Explanation of the memoization of Fibonacci numbers:

First we create an array $f$, to save the values that already computed. This is the main part of all memoization algorithms. Instead of many repeated recursive calls we can save the results, already obtained by previous steps of algorithm. As shown in the algorithm we set the $f[1],f[2]$ to $1$.

In the first if we actually check whether we are in the start or not. But we can remove this if statement. But for make it simpler to read I left it.

In the second if, we check if the value of fib(n) is already computed or not. This prevents us from multiple call for the same number, for example suppose we want to compute f(6), then in normal recursion we have the first recursion tree as shown in the following figure and in the memoization version we have the second tree. The reason is, in memoization we just compute the green vertices one time and then we save them into the memory (array $f$) and if needed we fetch them later.

In the following figure, green nodes are parts which are necessary to be computed (in this way), yellow nodes are precomputed ones, and red nodes are the nodes that are repeatedly computed in the first recursion.

As is clear from the image, in the normal case we have just precomputed f(1) and f(2), but in the memoization case, all functions for less than $n-1$ are precomputed, and this causes exponentially smaller recursion tree. (In memoization number of red nodes is zero, which is exponential in the normal recursion).

First tree is normal recursion tree, second one is by memoization.

$\endgroup$
  • $\begingroup$ I'm not sure this is correct. The recursive solution requires the stack to be stored, which likely uses more memory than the memoization's array. $\endgroup$ – Dukeling Jul 3 '13 at 12:09
  • $\begingroup$ @Dukeling, If you see my answer, I didn't say that in this case, I said sometimes. On the other hand you are right, memoization is very good even in memory, in most times. But I mentioned this to notify OP about the usage of this technique to reduce the time complexity (not memory). $\endgroup$ – user742 Jul 3 '13 at 12:14
  • $\begingroup$ Ok, the memoization code you provided does actually seem to use slightly more memory. But IMO it's a non-issue, since you can just use a simple for-loop to populate the array, which is faster and uses less memory than either. And this can further be optimized (assuming you only do a single call) to only store the last 2 values, thus constant space. $\endgroup$ – Dukeling Jul 3 '13 at 12:21
  • $\begingroup$ But a for-loop wouldn't be recursive any more, so I suppose this answer answers the question - I'm just not too fond of giving examples of things that can easily be done a lot better, even though Fibonacci numbers is a popular example for recursive functions. $\endgroup$ – Dukeling Jul 3 '13 at 12:28
  • 1
    $\begingroup$ @SaeedAmiri yes actually i'm having difficulty understanding the code.I will be very glad if you can please explain with proper code and comments. $\endgroup$ – Anirban Nag 'tintinmj' Jul 3 '13 at 16:53

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.