for (int i = 0; i < n; i  ) {}

There is nothing in the body of the loop, but I still think the complexity will be O(n). This is true?

CodePudding user response：

Yes.

As long as this loop is executed (and not e.g. optimized away by the compiler), it is indeed O(n). This is because a loop iteration has some overhead, such as performing the i operation.

CodePudding user response：

That's indeed true (with the additional note that the loop is executed, as @Berthur pointed out, so assuming that the compiler does not optimise).
Even though the body is empty, you are iterating from i = 1 to i = n. The for-loop brings the linear time complexity O(n) (note that the space complexity is O(1), assuming that the for-loop you've specified is the only piece of code in your program (so that there are no arrays, maps, etc))

CodePudding user response：

If your perspective is practical (how fast an actual program will execute), it depends on the compiler and/or runtime system. For instance, a Java compiler will most likely discard this code completely, since logically it doesn't do anything, and it will take zero time. If the compiler doesn't do any optimization, or if it follows a strict contract that says code must be executed even if it has no effect, the time is linear. If the code is executed by an interpreter, without compilation (although your int hints that it's a compiled language), it likewise depends on the optimization capability of the interpreter, but it's pretty common that interpreters don't do much optimization and therefore would take linear time.

If your perspective is theoretical, i.e., an algorithm theory assignment, it's not generally defined. It depends on weather the machine model takes possible optimization into account or not.