>"My rule of thumb here is that if I have to use a loop within a loop, that’s O(n^2)."
This might potentially do someone a disservice. The whole point of analysis is just that - to "analyze" the runtime and not resort to "rules of thumb."
The presence of nested for loops itself is not a good reason to declare something quadratic. Consider the following which is most certainly not O(N^2):
for (int i = 0; i < 1000; i++)
for (int j = n; j >= 1; j = j / 2)
// do something
EDIT: initialized j to the val of n on the inner loop per the comments below.
This might potentially do someone a disservice. The whole point of analysis is just that - to "analyze" the runtime and not resort to "rules of thumb."
The presence of nested for loops itself is not a good reason to declare something quadratic. Consider the following which is most certainly not O(N^2):
for (int i = 0; i < 1000; i++)
EDIT: initialized j to the val of n on the inner loop per the comments below.