# Function that grows slower than log, using exponentiation instead of multiplication

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.

-
What algorithm you doing? – PyRulez Oct 25 '13 at 19:48

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$.

-
Ahh, that makes sense. It wasn't obvious to me that 2^2^k = n implies k = log(log(n)), but I just worked it out and it looks right. I'm going to spend some time thinking about why it's right, so that it becomes more intuitive. Thanks a bunch! – FuriousGeorge Apr 21 '11 at 21:12