can you explain the time complexity of
void pat()
{ //executes log (input size) times
for (int i = 2; i <=n; i = pow(i, c))
{ System.out.print("")
}
//Here fun is sqrt or cuberoot or any other constant root //executes log n times
for (int i = n; i > 1; i = fun(i))
{
System.out.print("") }
}
}
i am gonna try to break it down line by line
for (int i = 2; i <=n; i = pow(i, c))
{ System.out.print("")
}
assume c =2 and n=some power of 2
first pass i =2;
second pass i =4
third pass i = 16
(raising powers by c)
… so on till i<=n, this is what the loop is
from this loop can i say that this loop for the last iteration is going to be
when i==n (assume corner case or the worst case), in this duration let us assume it ran for k times
then that means according to our constraints n = (2)^(2^k) think about it carefully try substituting a few values of k to understand this
therefore logn = 2^k and k = loglogn
now let us come to the second loop
for (int i = n; i > 1; i = fun(i))
{
System.out.print("") }
}
in simpler terms, this is just the reverse of the previous loop
again assume the same constraints
let n be some power of 2, let fun be square root
let us assume the case where i has to exactly 2(the last iteration) in the kth iteration
so 2 = (n)^((1/2)^k)
or alternately log2 = ((1/2)^k)logn
which is 2^(-k) = logn/log2
-klog2 = log(logn/log2)
and since it is time complexity we can take mode and ignore the constants so effectively
k = loglogn
so total complexity is loglogn
@dare_devil_007 if your doubt is solved, please mark it as resolved