Running time of a function of n with while loop

Question

Provide a tight Θ bound on the running time of the function of n.

a = n
   while ( a > 1 or a > 2 or a > 3)
      for b = 1 to n
         print "Hello World"
      a = sqrt(a)

Would the running time be dependent on the condition set in the while loop? Currently my answer for this is nlog(n) but I am not sure if that is correct? Can someone clarify? I thinking the sqrt makes it log(n)

Answer 1

The first inner loop (the one based on for b = 1 to n) uses n steps. Then n is replaced by sqrt(n) hence the second inner loop uses sqrt(n) steps, and so on. This shows the run time is n + sqrt(n) + sqrt(sqrt(n)) + ...

If n = 2^(2^k) then sqrt(n) = 2^(2^(k-1)), sqrt(sqrt(n)) = 2^(2^(k-2)), and so on, hence there are k terms in the sum above. Thus, for some general n, there are about log(log(n)) terms. Counting the first loop separately, one sees that the run time is more than n and less than n + sqrt(n) * log(log(n)). Finally, the run time is equivalent to n, in particular it is Θ(n).