Having trouble solving a complicated recurrence relation

114 Views Asked by At

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