Solve the recurrence F(n) >= 2 F(sqrt(n)) + lg n

Answer: Let m = lg n, and let G(m) = F(2^m) = F(n).
Then the recurrence becomes G(m) >= 2 G(m/2) + m

The solution is G(m) >= Omega(m log m)

Thus F(n) >= Omega(log n log log n)

It's Omega because it's >= instead of =