hello sir,
Predict time complexity:
for(i=2;i<n;pow(i,2)) { }
How is the time complexity for this code : O(nlog logn)??
Doubt in quiz question
it should be log logn
In this case, i takes values 2, 2^2, (2^2)^2 = 2^(2^2), (2^(2^2))^2 = 2^(2^3), …, 2^(2^log2(log(n)). The last term must be less than or equal to n, and we have 2^(2^(log2(log(n))) = 2^log(n) = n, which completely agrees with the value of our last term. So there are in total log(log(n)) many iterations, and each iteration takes a constant amount of time to run, therefore the total time complexity is O(log(log(n))).