Is this recurrence relation O(infinity)?

Question

Is this recurrence relation O(infinity)?

T(n) = 49*T(n/7) + n

There are no base conditions given.

I tried solving using master's theorem and the answer is Theta(n^2). But when solving with recurrence tree, the solution comes to be an infinite series, of n*(7 + 7^2 + 7^3 +...) Can someone please help?

Answer 1

Let n = 7^m. The recurrence becomes

T(7^m) = 49 T(7^(m-1)) + 7^m,

or

S(m) = 49 S(m-1) + 7^m.

The homogeneous part gives

 S(m) = C 49^m

and the general solution is

S(m) = C 49^m - 7^m / 6

i.e.

T(n) = C n² - n / 6 = (T(1) + 1 / 6) n² - n / 6.

Answer 2

If you try the recursion method:

T(n) = 7^2 T(n/7) + n = 7^2 [7^2 T(n/v^2) + n/7] + n = 7^4 T(n/7^2) + 7n + n

= ... = 7^(2i) * T(n/7^i) + n * [7^0 + 7^1 + 7^2 + ... + 7^(i-1)]

When the i grows n/7^i gets closer to 1 and as mentioned in the other answer, T(1) is a constant. So if we assume T(1) = 1, then:

• T(n/7^i) = 1
• n/7^i = 1 => i = log_7 (n)

So

T(n) = 7^(2*log_7 (n)) * T(1) + n * [7^0 + 7^1 + 7^2 + ... + 7^(log_7(n)-1)]

=> T(n) = n^2 + n * [1+7+7^2+...+(n-1)] = n^2 + c*n = theta(n^2)

Answer 3

Usually, when no base case is provided for a recurrence relation, the assumption is that the base case is something T(1) = 1 or something along those lines. That way, the recursion eventually terminates.

Something to think about - you can only get an infinite series from your recursion tree if the recursion tree is infinitely deep. Although no base case was specified in the problem, you can operate under the assumption that there is one and that the recursion stops when the input gets sufficiently small for some definition of "sufficiently small." Based on that, at what point does the recursion stop? From there, you should be able to convert your infinite series into a series of finite length, which then will give you your answer.

Hope this helps!