Nested Loop Time Complexity | Java Fresher Interview

To analyze a nested loop, my basic rule is to multiply the number of times each loop runs. If the outer loop runs n times and the inner loop also runs n times, that's n times n, so O of n squared. But I'm careful not to just count the nesting depth, because the inner loop's actual range is what matters. There are a few cases I distinguish. The straightforward case is both loops running fully from zero to n, which is clearly O of n squared. Then there's the triangular case, where the inner loop starts at the outer index, so for j from i to n. Here the inner loop runs n times, then n minus one, down to one, and that sum is n times n plus one over two. After I drop the constant, that's still O of n squared, even though it does about half the work of the full square. If the inner loop runs a fixed number of times, say always five, its work does not grow with n. Then the total is n times five, which is just O of n, linear, even though it looks like a nested loop. And if the two loops use different sizes, say n and m, it's O of n times m, not O of n squared. There's also the case where the inner loop halves a value each step, which is log n, making the whole thing O of n log n. So my approach is always to read the inner loop's bound carefully and ask whether it depends on n, on the outer index, or is just a constant.