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

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ⁿ + 2^n-2 + 2^n-3 + ... + 1

Therefore, the tightest bound is Θ(2ⁿ).