How expensive are for and while loops?

Question

The question is asking for a comparison between costs of for and while loops, relative to the cost of if statements.

Say an if statement has a relative cost of 1, what's the relative cost of for and while loops?

Assume that a single boolean value is being passed onto the while loop and if statement when comparing and the while is allowed to iterate X times. Assume that the for also iterates X number times.

[Microoptimizations are evil](http://blog.codinghorror.com/the-sad-tragedy-of-micro-optimization-theater/) — Alex Shesterov, Nov 18 '14 at 16:41
Mostly a duplicate of http://stackoverflow.com/questions/1165457/java-for-loop-vs-while-loop-performance-difference — The Archetypal Paul, Nov 18 '14 at 16:42
How is this getting 8 downvotes? It's not even a bad question.. — ThePixelPony, Nov 18 '14 at 16:43
@ThePixelPony - it doesn't show a ton of effort though. research and code and such silly stuff — Caffeinated, Nov 18 '14 at 16:43
@Paul Just a single `boolean` variable. Example: boolean yes = true; while(yes) etc — ThePixelPony, Nov 18 '14 at 16:44
It's a dreadful question. Please explain why you're asking. A for-loop isn't obviously comparable to a if statement, for a start — The Archetypal Paul, Nov 18 '14 at 16:44
And what happens to that single boolean value in the loop? If not modified, they're all basically if statements. If modified, the if statement executes once, the while /for potentially many times (obviously, which is why it really isn't clear what you're actually asking) — The Archetypal Paul, Nov 18 '14 at 16:47
@Coffee I suppose but it's a pretty simple question; there isn't really much else that I could have added to be honest. — ThePixelPony, Nov 18 '14 at 16:47
@Paul, well, it's asking to compare a while and for loop, relative to an if statement. — ThePixelPony, Nov 18 '14 at 16:48
But they're not comparable! An if statement executes at most once, a for/while loop potentially many times. — The Archetypal Paul, Nov 18 '14 at 16:49
@Paul Looks like I didn't phrase this too well. I was referring to the cost. *Say an `if` statement has a relative cost of 1, what's the relative cost of `for` and `while` loops?* The current answer covers this. — ThePixelPony, Nov 18 '14 at 16:55
time complexity is n of loops so compare that to if statements — jgr208, Nov 18 '14 at 16:57
@laiello I have tried to rephrase my quesiton to make it more clear. — ThePixelPony, Nov 18 '14 at 16:59

Lawrence Aiello · Accepted Answer · 2014-11-18T16:46:39.673

9

In terms of performance, if statements are usually of O(1) complexity, where as for and while loops are usually O(n), where n is the amount of loops it takes depending on what the conditions are. For example:

for (int i = 0; i < 100; i++)
{
    // Some statements
}

Would be O(100), because it is looped through 100 times. It does not matter how many statements are inside the for loop, unless there are additional loops inside the initial loop. Then you get to O(n^2) complexity, which is quadratic and thus highly inefficient.

However, do not let this scare you. Loops exist for a reason, and they are necessary in many programs.

edited Nov 18 '14 at 16:46

answered Nov 18 '14 at 16:40

Lawrence Aiello

4,560
5
21
35

@laiello - Nah .. I know. just too brief is all. maybe we judge quickly – Caffeinated Nov 18 '14 at 16:46
also if you need to loop 100 times it would certainly be more clean then 100 if statements. also you will barely notice these time differences with todays computers unless you are doing something very intensive. – jgr208 Nov 18 '14 at 16:58
I agree, but I implore you to go to an algorithms professor and say to him "Loop complexity does not matter". Maybe not for overall programs, but in Computer Science, it is very important. – Lawrence Aiello Nov 18 '14 at 17:07

Sotirios Delimanolis · Answer 2 · 2014-11-18T17:04:45.110

Loops are language constructs. You can write a while loop to do the same thing as a for loop and vice versa.

Say an if statement has a relative cost of 1, what's the relative cost of for and while loops?

for loops and while loops also check a condition. In that sense, they also have a cost of 1. The point is that there is typically something in the loop that will affect that condition.

Consider this code

public static void main(String[] args) throws Exception {
    for (int i = 0; i < 10; i++) {

    }

    System.out.println("");

    int i = 0;
    while (i < 10) {
        i++;
    }
}

The bytecode generated is

    // start for
     0: iconst_0
     1: istore_1
     2: iload_1
     3: bipush        10
     5: if_icmpge     14
     8: iinc          1, 1
    11: goto          2
    // end for
    14: getstatic     #2                  // Field java/lang/System.out:Ljava/io/PrintStream;
    17: ldc           #3                  // String
    19: invokevirtual #4                  // Method java/io/PrintStream.println:(Ljava/lang/String;)V
    // start while
    22: iconst_0
    23: istore_1
    24: iload_1
    25: bipush        10
    27: if_icmpge     36
    30: iinc          1, 1
    33: goto          24
    36: return
    // end while

You'll notice both loops do the exact same thing and generate the exact same bytecode.

How expensive are for and while loops?

2 Answers2