One way to think about this question is to break the range that j starts from and ends at, into two parts:
j starts from 1, reaches n.
Let us break this into two separate journeys:
- Part 1: j goes from 1 to sqrt(n)
- Part 2: j goes from sqrt(n) to n.
Let us analyze these two separately.
- Part 1 - This can not take more than O(sqrt(n)) time
- Part 2 - This can not take more than O(n / log (sqrt(n))) time.
We observe that O(n/log (sqrt(n))) = O( 2 n / log n) = O(n / log n) time.
Therefore, total time = O(sqrt(n)) + O(n/log n), that is, O(n/log n)