# Determine the time complexity of this algoritm (pseudocode)

{
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?

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}$$
• 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))$ Oct 17 at 19:26