What is the time complexity for n here? I feel the outer loop is logn and inner is logn as they both have x and y increase in square of two every step, yet could it possible for both outer and inner be sqrt of n and together is O(n).
Time complexity — cannot determine whether it is logn or sqrt n
Viewed 64
1 Answers
It's pretty clear that the outer loop will run exactly sqrt(n) times. For each of the outer loops, there is an inner loop that also runs exactly sqrt(n) times. The total time is thus sqrt(n)*sqrt(n), which as you note is n.
Related