2

I tried to solve this recursion equation with master theory, and it's not working in this way.

How many arrays exist in each step in the recursion tree?

And how can I solve this problem with another way?

tinlyx
  • 1,534
user11001
  • 123
  • 1
    Please look at the definition of a tag before using it: (theta-functions) is something else. – Did Dec 05 '14 at 22:42

1 Answers1

1

The direct way: consider the change of variable $$S(n)=\frac{T(n)}n-2\log n.$$

Did
  • 279,727
  • 1
    thanks , can u be please more specific? – user11001 Dec 05 '14 at 22:51
  • 1
    Sure: did you try to write $S(n)$ in terms of $S(\sqrt{n})$? If you did, please write here the recursion you got. (A downvoter seems to think this is too much to ask to do.) – Did Dec 06 '14 at 07:42