1
$\begingroup$
{
t <- n
while t>1 do
  t <- log_2(t)
}

I tried to do it this way: $f^\text{(1)}(t)=\log_2(t) \\ f^\text{(2)}(t)=\log_2\log_2(t) = \log_2^{(2)}(t) \\f^\text{(3)}(t) = \log_2^{(3)}(t) \\ f^\text{(j-1)}(t) = \log_2^{(j-1)}(t) \\ f^\text{(j)}(t) = \log_2\log_2^{(j-1)}(t) = log_2^{(j)}(t) $ Note: I consider $f^{(j)}(t)$ the function $f(t)$ iterated $j$ times.

Now I need to find out $min\{j:f^{(j)}(t) > 1\} = min\{j:\log_2^{(j)}(t) > 1\}$

But I can't find a way to determine $j$, so I think there's a different way to calculate the complexity of this algorithm, some idea?

$\endgroup$
1
0
$\begingroup$

I got it: this algorithm has a nearly-constant complexity, specifically the complexity is $\Theta(\log^{*}(n))$ where $\log^{*}(n) \le 5 \ \forall n \le 2^{16}$

$\endgroup$
2
  • 1
    $\begingroup$ How long does it take to calculate log_2 (n)? Surely not constant time? $\endgroup$
    – gnasher729
    Oct 17 at 17:39
  • $\begingroup$ It surely takes $O(\log(n))$ time to calculate that (just check how many bits are present. So if you want to also consider the time that is spent on calculating the logs, the answer will be $O(\log(n)\log^*(n))$ $\endgroup$
    – nir shahar
    Oct 17 at 19:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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