Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
What algorithm you doing? –  PyRulez Oct 25 '13 at 19:48
add comment

1 Answer

up vote 5 down vote accepted

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.