Recursion and Big O

Question

I've been working through a recent Computer Science homework involving recursion and big-O notation. I believe I understand this pretty well (certainly not perfectly, though!) But there is one question in particular that is giving me the most problems. The odd thing is that by looking it, it looks to be the most simple one on the homework.

Provide the best rate of growth using the big-Oh notation for the solution to the following recurrence?

T(1) = 2

T(n) = 2T(n - 1) + 1 for n>1

And the choices are:

• O(n log n)
• O(n^2)
• O(2^n)
• O(n^n)

I understand that big O works as an upper bound, to describe the most amount of calculations, or the highest running time, that program or process will take. I feel like this particular recursion should be O(n), since, at most, the recursion only occurs once for each value of n. Since n isn't available, it's either better than that, O(nlogn), or worse, being the other three options.

So, my question is: Why isn't this O(n)?

Answer 1

I think this will be exponential. Each increment to n makes the value to be twice as large.

T(2) = 2 * T(1) = 4
T(3) = 2 * T(2) = 2 * 4
...

T(x) would be the running time of the following program (for example):

def fn(x):
 if (x == 1):
  return    # a constant time
 # do the calculation for n - 1 twice
 fn(x - 1)
 fn(x - 1)

Answer 2

I think you have misunderstood the question a bit. It does not ask you how long it would take to solve the recurrence. It is asking what the big-O (the asymptotic bound) of the solution itself is.

What you have to do is to come up with a closed form solution, i. e. the non-recursive formula for T(n), and then determine what the big-O of that expression is.

Answer 3

I think this will be exponential. Each increment to n brings twice as much calculation.

No, it doesn't. Quite on the contrary:

Consider that for n iterations, we get running time R. Then for n + 1 iterations we'll get exactly R + 1.

Thus, the growth rate is constant and the overall runtime is indeed O(n).

However, I think Dima's assumption about the question is right although his solution is overly complicated:

What you have to do is to come up with a closed form solution, i. e. the non-recursive formula for T(n), and then determine what the big-O of that expression is.

It's sufficient to examine the relative size of T(n) and T(n + 1) iterations and determine the relative growth rate. The amount obviously doubles which directly gives the asymptotic growth.

Answer 4

The question is asking for the big-Oh notation for the solution to the recurrence, not the cost of calculation the recurrence.

Put another way: the recurrence produces:

  1 -> 2
  2 -> 5
  3 -> 11
  4 -> 23
  5 -> 47

What big-Oh notation best describes the sequence 2, 5, 11, 23, 47, ...

The correct way to solve that is to solve the recurrence equations.

Answer 5

There's a couple of different ways to solve recurrences: substitution, recurrence tree and master theorem. Master theorem won't work in the case, because it doesn't fit the master theorem form.

You could use the other two methods, but the easiest way for this problem is to solve it iteratively.

T(n) = 2T(n-1) + 1
T(n) = 4T(n-2) + 2 + 1
T(n) = 8T(n-3) + 4 + 2 + 1
T(n) = ...

See the pattern?

T(n) = 2^(n-1)T(1) + 2^(n-2) + 2^(n-3) + ... + 1
T(n) = 2^(n-1)2 + 2^(n-2) + 2^(n-3) + ... + 1
T(n) = 2^n + 2^(n-2) + 2^(n-3) + ... + 1

Therefore, the tightest bound is Theta(2^n).

Answer 6

First off, all four answers are worse than O(n)... O(n*log n) is more complex than plain old O(n). What's bigger: 8 or 8 * 3, 16 or 16 * 4, etc...

On to the actual question. The general solution can obviously be solved in constant time if you're not doing recursion

( T(n) = 2^(n - 1) + 2^(n) - 1 ), so that's not what they're asking.

And as you can see, if we write the recursive code:

int T( int N )
{
    if (N == 1) return 2;
    return( 2*T(N-1) + 1);
}

It's obviously O(n).

So, it appears to be a badly worded question, and they are probably asking you the growth of the function itself, not the complexity of the code. That's 2^n. Now go do the rest of your homework... and study up on O(n * log n)

Answer 7

Computing a closed form solution to the recursion is easy. By inspection, you guess that the solution is

T(n) = 3*2^(n-1) - 1

Then you prove by induction that this is indeed a solution. Base case:

T(1) = 3*2^0 - 1 = 3 - 1 = 2. OK.

Induction:

Suppose T(n) = 3*2^(n-1) - 1. Then
T(n+1) = 2*T(n) + 1 = 3*2^n - 2 + 1 = 3*2^((n+1)-1) - 1. OK.

where the first equality stems from the recurrence definition, and the second from the inductive hypothesis. QED.

3*2^(n-1) - 1 is clearly Theta(2^n), hence the right answer is the third.

To the folks that answered O(n): I couldn't agree more with Dima. The problem does not ask the tightest upper bound to the computational complexity of an algorithm to compute T(n) (which would be now O(1), since its closed form has been provided). The problem asks for the tightest upper bound on T(n) itself, and that is the exponential one.