1

I would like to solve the relation:

$T(n^6) = 9T(n^{\frac{1}{6}}) + \log^2_2(n)$

Now upon searching, I found that such relations can be solved using iteration method and making a substitution, hence I tried substituting $m = \log_2 n$. This gives the relation:

$T(64^m) = 9T(2^{\frac{m}{6}})+m^2$. Am I solving this correctly?? How do I proceed further? Please help, I am not good at this.

Rick
  • 1,099
  • That's a good start, now keep going. You can apply the recurrence to $T(2^{m/6})$ to express it in terms of $T(2^{m/216})$, and so on and so forth. – Qiaochu Yuan Sep 14 '19 at 02:49
  • @QiaochuYuan Also, in the original question, the logarithm base was not given, I took it to be $2$ as done in some text online, would taking any other base be helpful? Like $6$ for instance? – Rick Sep 14 '19 at 02:53
  • The title does not appear to match the post. Qlso it may be easier to consider the function defined by $g(n)=T(2^{36^n})$. – Simply Beautiful Art Sep 14 '19 at 02:59

1 Answers1

2

$T(n^6) = 9T(n^{\frac{1}{6}}) + \log^2_2(n) $

Put $n = 2^{2^m} $. $\log_2n = 2^m $.

Becomes $T((2^{2^m})^6) = 9T((2^{2^m})^{\frac{1}{6}}) + 2^{2m} $ or $T(2^{6\cdot 2^m}) = 9T(2^{2^m/6}) + 2^{2m} $.

Try $n = 2^{6^m} $. $\log_2n = 6^m $.

Becomes $T((2^{6^m})^6) = 9T((2^{6^m})^{\frac{1}{6}}) + 6^{2m} $ or $T(2^{6^{m+1}}) = 9T(2^{6^{m-1}}) + 6^{2m} $.

Let $U(m) =T(2^{6^m}) $. Then $U(m+1) = 9U(m-1) + 6^{2m} $.

This is readily solved.

marty cohen
  • 107,799