These type of recursions can be solved by unrolling the recursion, spotting the similarities between elements.
Now at some point the recursion will exhaust itself. This will happen if T(...) = T(a) = b
. Any reasonable a
will work, so I selected 2. Solving the equation n^(1/2^k) = 2
by taking log
of both sides, you get: k = log(log(n))
. Now substitute it back in your recursion:
Limit of 2^(-loglogn)
is equal to 0
if n -> infinity
, so the first element in summation is equal to b. The complexity is O(n * log log (n))