CODEWITHSUNDEEP
algorithmtime-complexity
man
man

Reputation: 77

What is the complexity of the algorithm without body in for loop?

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

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

Upvotes: 3

Views: 117

Answers (3)

njlarsson
njlarsson

Reputation: 2340

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.

Upvotes: 2

Vlad Nitu
Vlad Nitu

Reputation: 167

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))

Upvotes: 3

Berthur
Berthur

Reputation: 4495

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.

Upvotes: 5

Related Questions