Runtime of a recursive function involving square roots?

Question

Can anyone help me to find the time complexity of the following recursive function? I wrote T(n^(1/2)), T(n^(1/4)),... T(1) recursively but what is the general way to get to the runtime of any recursion?

T(n) = n^(1/2) (T(n^(1/2)) + n

Answer 1

The other answers here give a great algebraic intuition and solution to this problem. Here's another way to see this in terms of recursion trees.

When you have a recurrence relation, it's often useful to draw a picture of the recursion tree to see what it looks like. Here, the recursion tree looks something like this:

                        +-------+
                        |   n   |
                        +-------+
         /       /          |          \           \
     +-------+ +-------+ +-------+           +-------+
     |n^(1/2)| |n^(1/2)| |n^(1/2)|    ...    |n^(1/2)| 
     +-------+ +-------+ +-------+           +-------+
       ...        ...       |                   ...
         /       /          |          \           \
     +-------+ +-------+ +-------+           +-------+
     |n^(1/4)| |n^(1/4)| |n^(1/4)|    ...    |n^(1/4)| 
     +-------+ +-------+ +-------+           +-------+

So let's think about this tree. The top level consists of a single call that does O(n) work. At the next level, there are √n recursive calls, each of which does √n work. That's a total of O(n) total work. At the level below that, each of the √n recursive calls will make ⁴√n recursive calls to problems of size ⁴√n. If we group them together, we get √n groups of ⁴√n recusive calls doing ⁴√n work each. That's √n groups of recursive calls doing √n work each - another O(n) total work.

More generally, as you walk down the recursion tree, you'll find that each level does O(n) work. So that means that the total work done by the recursive calls will be equal to O(n) times the number of layers in the tree. Now we just need to figure that out.

It turns out that the number of times you can take the square root of a number before it drops down to a constant is O(log log n). (The linked answer has the math behind this worked out). That means that we'd expect the total work done to be O(n log log n) - there are O(log log n) layers in the tree, each of which does O(n) work.

The math that the other answers have included here formalizes this reasoning, but I figured it might be helpful to see things this way so that you can see where that answer comes from.