title: How to get the time complexity of this recurrence: T(n) = sqrt(n) * T(sqrt(n)) + n
body: <p>This recurrence:</p>
  
  <p><code>T(n) = sqrt(n) * T(sqrt(n)) + n</code></p>
  
  <p>It does not appear to be solvable with Master theorem. It also does not appear to be solvable with Akra-Bazzi. Even if I set n = 2^k so that <code>T(2^k) = 2^(k/2) * T(2^(k/2)) + 2^k</code> and then have <code>S(k) = T(2^k)</code> it becomes <code>S(n) = 2^(n/2) * S(n/2) + 2^n</code> but the multiplier is not constant, so changing variables doesn't work either.</p>
  
  <p>I am not sure how to derive the closed form, or the time complexity, of this recurrence, if it had been given to me in an interview. What would you do?</p>