mathbig-odiscrete-mathematicsrecurrencemaster-theorem

Is this recurrence relation O(infinity)?

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?

Solution

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