0

Original equation: $T(n) = n^{2/3}T(n^{1/3})+n$

My work:

= $n^{2/3}(T(n^{1/3})+n^{1/3})$

= $n^{2/3}(n^{2/9}(T(n^{1/3})+n^{1/9})+n^{1/3})$

= $n^{2/3}(n^{2/9}(n^{2/81}(T(n^{1/81})+n^{1/81})+n^{1/9})+n^{1/3})$

My problem is I don't know how to generalize this pattern. It seems that there is a $n^{2/(3^{k})}$ term, but is k multiplied by 2 or is it squared? Also, I am having trouble writing this recursive summation. Can someone give me a hint on how to approach this?

EDIT: Base case is T(n) = 1 for n <= 5

Jeremy Fisher
  • 153
  • It seems that there is some problem with $n=1$, $T(1) = T(1) +1 $ ??!!? – mastrok Sep 08 '15 at 03:01
  • sorry i forgot to add the base cse – Jeremy Fisher Sep 08 '15 at 03:08
  • Yeah, but that still gives $1 = T(1) = T(1) + 1 = 2$, which is not going to work. (This is what @mastrok was getting at: there's no $x$ satisfying $x=x+1$.) – Eric Towers Sep 08 '15 at 04:21
  • If values of n are integers, then what happens when n is not a power of 3, hence n^(1/3) is not an integer, hence T(n^(1/3)) is not defined? – philophilosophia Sep 09 '15 at 19:44
  • 1
    "Can someone give me a hint on how to approach this?" Consider $$S(n)=\frac{T(n)}n$$ and note that the relation on $T$ translates into $$S(n)=S(n^{1/3})+1$$ – Did Sep 13 '16 at 17:02

0 Answers0