Jasmine Jasmine - 1 year ago 85
Java Question

Big O of a for loop with a false condition

I just need some clarification or help on this Big O problem. I don't know if I'm explaining this correctly, but I noticed that the for loop has a false condition, so that means it won't loop at all. And my professor said it's possible to still determine the run time of the loops. So what I'm thinking is this:

1 + (n - 1 - n) * (n) = 1 + 1 * n = 1 + n = O(n)

Explanation: 1 is for the operation outside of the loop. (n - 1 - n) is the iteration of the outer loop and n is the iteration of the inner loop.

Note: I'm still learning Big O, so please correct me if any of my logic is wrong.

int total = 0;
for (int i = n; i < n - 1; i++) {
for (int j = 0; j < n; j++) {
total = total + 1

Answer Source

There shouldn't be any negative number in Big O analysis. It doesn't make sense for negative running time. Also, (n - 1 - n) is not just in order O(1). Your outer loop doesn't even go into one iteration. Thus, the time complexity for whatever statement in your loop doesn't matter.

To conclude, the running time is 1 + 1 = O(1).

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download