[Math] Function that grows slower than log, using exponentiation instead of multiplication

Question

I'm trying to solve a problem by dividing it into chunks, until each chunk is of size 2 or less, at which point each chunk is easy to solve. I'm having trouble with how to mathematically represent how many such divisions I need to make for some initial problem size n.

For most problems I deal with, I break the problem in half continuously until I reach the trivial sizes, so I would say there are log(n) divisions.

But with this problem, I'm taking the square root of the problem size in each chunk. So the number of divisions can be represented as "how many times do I need to take the square root of n for n becomes <=2", or alternatively, "how many times do I need to square 2 before it becomes >=n". This function f(n), whatever it is, obviously grows slower than log(n), but I don't know of a function with this name, nor can I figure out how I would represent it mathematically.

Answer 1

If you square $\displaystyle 2$, $\displaystyle k$ times, you get $\displaystyle 2^{2^k}$.

Thus you need

$$ 2^{2^k} \ge n$$

i.e.

$$ k \ge \log_2 (\log_2 n)$$

and so you can pick

$$ k = \lceil \log_2 (\log_2 n) \rceil$$

Where $\displaystyle \log_2$ is log to base $\displaystyle 2$.