in Q14 the two loops will run individually run and each take logn time then the overall tc would be logn but the answer is different
Time complexity
@paidaarpit1505_f9664148aad841e0
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
1 Like
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.