2
$\begingroup$

This is my first question on this site... yesterday I asked this on cs.so but they downwote and told me that so.cs is a research-level site, not for students... I hope it's appropriate to ask this question here ...

I'm looking for a general way to solve recursions with non-equal exponents on left and right. for example: $ \mathrm{T}(n^a)=c\mathrm{T}(n^b)+\mathrm{P}_d(n)\;\;\;\; a \neq b $

for example:

$ T(n) = 4T(\sqrt{n})+1 , \;\; (n>2) $

$ T(2)=1, \;\; (n \leq 2) $

  • 0
    I'm sorry, but this is a student-level site, not for research. (just kidding)2011-10-19

1 Answers 1

2

Only answering the example.

Hint: What do you get, when you substitute $n=2^{2^k}$? Can you fill in the gaps? Try with small inputs $n=3,5,6,\ldots$ outside the set of values described in the first suggestion.