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
    Off-topic. Is there a particular reason why you use `\mathrm` in your LaTeX for `T` and `P`? I am just curious. :)2011-10-18
  • 0
    So where should I get the answer or a start point, reference, etc? and no! there is no reason else than I don't like Italic things :-/2011-10-18
  • 0
    What is $P_d$ ?2011-10-18
  • 0
    @Phira: a $d$-degree polynomial of $n$.2011-10-18
  • 0
    What kind of functions on which domain are you looking for? Do you have an example? Are the functions continuous? Or functions on the natural numbers ? Are there initial conditions?`Are you looking for asymptotics?2011-10-18
  • 0
    @Phira: What? $T(n)$ is $n$th term! isn't this obvious?2011-10-18
  • 0
    Oh! all terms are positive. they are in $\mathbb{N}$ and I'm trying to find the big-oh of recurrence.2011-10-18
  • 0
    @Sorush As indicated by the other comments, your question is poorly asked. I recommend reading other questions so you can see how to ask a good one. In particular you should explain what your symbols mean. Since many questions on math.stackexchange are also poorly worded, you might want to try [MathOverflow](http://mathoverflow.net/) (MO) instead. In particular, MO has a nice [how to ask](http://mathoverflow.net/howtoask) page.2011-10-18
  • 0
    @QuinnCulver. OK. Thank you for link :)2011-10-18
  • 0
    I think that the question is on-topic here even if it was originally formulated a bit unclearly. I don't know much general theory, but the structure of the example recurrence relation suggests first looking at the function $S(k):=T(2^{2^k})$. I collected this and another hint to an answer. So compute $S(0)=T(2)$, $S(1)=T(4)$, $S(2)=T(16)$ first, and see if you see a more familiar recurrence relation there. Ask, if you can't make any headway.2011-10-18
  • 0
    I'm sorry, but this is a student-level site, not for research. (just kidding)2011-10-19

1 Answers 1