Solving the recurrence T(n) = 2T(sqrt(n))+log2n

1
votes

I would like to solve the following recurrence relation:

T(n) = 2T(sqrt(n))+log2n

Unfortunately, neither the master theorem nor the akra-bazzi-method can be applied in this case. I guess that the solution must be O(log log n) but I am not sure how to prove this.

Many thanks in advance.

1
mathbig-orecurrence
I'm voting to close this question as off-topic because it is about Mathematics instead of programming or software development. - Pang

1 Answers

4
votes

Make the substitution:

enter image description here

Then the recurrence becomes:

enter image description here

We'll assume here that log is base 2, WLOG.

enter image description here

There are log(m) of these terms (ignoring off-by-one etc.), so:

  • The m terms sum to m log(m)
  • The "constant" terms are a geometric series, and sum to

enter image description here

(... so we ignore it)

Thus the overall complexity is:

enter image description here