For

A for loop in programming language is a control statement which allows programmer to execute a set of codes repeatedly. It functions just like while loop, but the for loop is usually used when we know the number of times we want to execute the body of the loop.

The following graphic represents the control flow of a for loop. It mimics this Python code:

1
2

for i in range(0, 3):
    print i

For Loop Flow

The exact syntax of the for loop varies from language to language, but the overall protocol is the same. First, the for loop defines the loop control variables that it needs to define the number of times it will execute. In the case of the above code, the control variable is i. This is a notable difference from the while loop whose statement does not provide a set number of loops nor any control variables. Then, the code within the for loop is executed the appropriate amount of times.

For loops are a critical statement for any programming language and are used in most, if not all programs. They can be thought of as a specific type of while loop, where the halting condition is simply defined by the loop variable and a boolean statement. In the case of the above code, the halting condition is when i = 3. When that happens, the loop stops. They are, however, more common than while loops in modern programming.

The for loop statement has three main parts that are labelled in the picture below. This picture describes the syntax for Java, and the syntax will vary from language to language. All languages, however, have these parts, even if they are implied.

For loop parts

The first part introduces the for loop variable and sets the loop variable value (in this case to 0). For example, in the following for loop declaration (in java)

1

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

the for loop is initialized with a loop variable i. This variable starts at 0. The same declaration can be done in Python (though it's less verbose)

1

for i in range(1, 10):

Initially, the halting condition is evaluated. If it is true, the body of the loop is executed. If it is false, the body of the loop does not execute and the flow of control jumps to the next statement just after the for loop. For example, if this was the for loop

1

for (int i = 15; i < 10; i++) {}

the loop would not execute even once (because the initial value of i, 15, already triggers the halting condition i < 10.

After the body of the for loop executes, the flow of control jumps back up to the increment statement. This statement allows you to update any loop control variables. In Java, the ++ syntax means that you want to increase the value of your looping variable by 1 every time the loop executes. In Python, the looping variable increases by 1 implicitly every time.

The halting condition is now evaluated again. If it is true, the loop executes and the process repeats itself (body of loop, then increment step, and then again condition). After the condition becomes false, the for loop terminates.

The code that is being executed by the loop needs to go in certain places depending on which language you use. In Java, for instance, the code goes in the curly brackets shown at the end of the loop declaration. In Python, it is important to indent your code correctly so the for loop knows where to find the correct code. The following snippets of code in Java and Python do the same thing: they print out numbers 1 through 10.

Note: In Python, range is exclusive, so it won't execute on the last number, when i = 11.

Java

1
2
3

for (int i = 0; i <= 10; i++) {
    System.out.println(i.toString());
}

Python

1
2

for i in range(1, 11):
    print i

for loops are very similar to while loops. They both define a block of code to be run a repeated amount of times. However there are few main differences between the two.

The number of times a for loop iterates is well defined. That means that before the code even runs, we know how many times the loop will execute. while loops, on the other hand, can run indefinitely.

while loops do not have a loop control variable ike for loops do. This makes sense because the loop control variable defines the number of times the loop's code will execute, and that number is not well defined for while loops.

The halting condition for for loops and while loops do similar things. They both are evalated using a boolean statement. When that halting condition is met, the loop stops executing.

As an example, here are two loops in Python that do the same thing. They print out all of the numbers between 1 and 100 that are divisible by 7.

for loop

1
2
3

for x in range(1, 101):
    if x % 7 == 0:
        print x

*while loop

1
2
3
4

x = 0
while x <= 100:
    if x % 7 == 0:
        print x

These loops look very similar, but a variable, x, was needed in the while loop to facilitate the halting condition. For this example, for loops are more appropriate.

Traditional for loops have the format discussed above:

1
2
3

for(Init; condition; increment){
  //statment(s)
}

Write a "for" loop to calculate $2^8$ in C.

---

1 2 3 4 5 6 7

int i; int answer; for(i=1,answer=1;i<=8;i++){ answer = answer*2; }

Finally the answer will acquire the value of $2^8$ = 256. $_\square$

Suppose a person wants to add all the positive integers till 100. How can this be done in Python?

---

There is a simple formula for this: $n(n+1)/2$.

But you can also use the for loop to get an answer.

1 2 3 4

sum = 0 for i in range(1, 101): sum += i print sum

$_\square$

Iterator-based for loops

An iterator is an object in computer programming that allows itself to be traversed. A common example is the list in Python. A list is a linear data structure that holds values. A list of numbers, $A$, might look something like this:

A = [1, 4, 6, 2]

One way to to iterate over this list and print all of its elements is using the traditional for loop shown above. That code in Python would look like this:

1
2
3

A = [1, 4, 6, 2]
for x in range(0, len(A)):
    print A[x]

In this code, the indexes of the lists are used to get the elements out of it. But that's sort of clunky. There's a cleaner way of printing out the elements in A, and it's using iterator for loops.

1
2
3

A = [1, 4, 6, 2]
for x in A:
    print x

Using this iterator based approach, the programmer can skip the annoyances of getting list length and indices. Instead, we simply ask for each element in the list in order. Note that iterator based for loops are only available in some languages, so be sure to do you research before you start coding.

Consider the previous example of adding up all the positive integers till $100.$ Now write a Python version that is equivalent to the previous solution.

---

Before solving the this problem let us introduce a built-in function, range(). It is used to generate a list in arithmetic progression.

1 2	>>> range(5) [0, 1, 2, 3, 4]

range(n) is used to generate a list of numbers starting with $1$ and ending with $n-1$, but it can also take two or three arguments. range(begin, end), range(begin, end, step).

1 2 3 4

>>> range(3,8) [3, 4, 5, 6, 7] >>> range(6,20,3) [6, 9, 12, 15, 18]

The range() function can be used with a for statement, to supply a sequence of numbers from $1$ to $100$. Again, Python is exclusive.

1 2 3 4 5

n = 101 sum = 0 for i in range(1,n): sum = sum + i print sum

Analyzing the runtime of for loops (how long the loop takes to complete) is very important. As a programmer, you should always be aware of long your code takes to run. Also, for loops analysis is often used when analyzing algorithms.

$O(1)$: A loop or that runs a constant number of times is considered as $O(1)$. For example the following loop is $O(1)$.

1
2
3

   for (int i = 1; i <= 5; i++) {  
        // some O(1) expressions
   }

$O(n)$: Time complexity of a loop is considered as $O(n)$ if the loop variables is incremented/decremented by a constant amount. For example following functions have $O(n)$ time complexity.

1
2
3
4
5
6
7

   for (int i = 1; i <= n; i += c) {  
        // some O(1) expressions
   }

   for (int i = n; i > 0; i -= c) {
        // some O(1) expressions
   }

$O(n^{c})$: Time complexity of nested loops is equal to the number of times the innermost statement is executed. For example the following sample loops have $O(n^2)$ time complexity.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

   for (int i = 1; i <=n; i += c) {
       for (int j = 1; j <=n; j += c) {
          // some O(1) expressions
       }
   }

   for (int i = n; i > 0; i += c) {
       for (int j = i+1; j <=n; j += c) {
          // some O(1) expressions
        }
   }

$O(\log n)$: Time complexity of a loop is considered as $O(\log n)$ if the loop variables is divided or multiplied by a constant amount.

1
2
3
4
5
6

   for (int i = 1; i <=n; i *= c) {
       // some O(1) expressions
   }
   for (int i = n; i > 0; i /= c) {
       // some O(1) expressions
   }

$O(\log \log n)$: Time complexity of a loop is considered as $O(\log \log n)$ if the loop variables are reduced or increased exponentially by a constant amount.

1
2
3
4
5
6
7
8

   //  c is a constant greater than 1   
   for (int i = 2; i <=n; i = pow(i, c)) { 
       // some O(1) expressions
   }

   for (int i = n; i > 0; i = sqrt(i)) { 
       // some O(1) expressions
   }

Given two or more loops that are non-nested the sum of the complexity is equal to the complexity of the sum. For example:

1
2
3
4
5
6
7

   for (int i = 1; i <= m; i += c) {  
        // some O(1) expressions
   }

   for (int i = n; i < n; i += c) {
        // some O(1) expressions
   }

Here clearly the time complexity of the first loop is $O(n)$ and that of the second it $O(m)$, and therefore

$$O(n)+O(m)=O(n+m).$$

Sometimes it will be necessary to break or change the execution of the for loop early. Each language has its own ways of doing so. In Python, you can break, or stop, the execution of the code with the break statement.

1
2
3
4

for x in range(0, 20):
    if x == 5:
        print "Stop!"
        break

This will stop the for loop early, when x is equal to 5.

You can also decide to skip part of the loop code and go right to the next iteration of the loop using the continue statement. For example,

1
2
3
4

for x in range(0, 20):
    if x > 10:
        continue
    print "x is still small!"

In this code, the string "x is still small!" will only be printed out 10 times, not 20. This is because once x is above 10, the continue statement is executed, which skips all of the code below it and runs the next iteration of the for loop.

1. Write a function that takes in a list of integers. This function should return an integer that is equal to twice the aggregate sum of each value in the array. However, you can only traverse the array once with one for loop.

Show Answer

An answer to this question in Python might look like this:

1 2 3 4 5 6

def double_sum(A): sum = 0 for i in range(0, len(A)): sum += A[i] sum += A[len(A) - 1 - i] return sum