Algorithm Run Time - From a Specific Action to Steps

Computing power is a known limitation when programming. Though for the untrained eye, computers seem vastly powerful, when programming you are trying to reduce both the load on the processor and the running time. As we use less resources, we will have time to do more at the same time, and in less time. That is the rationale behind analyzing the run time of algorithms and code in general. When talking about code, there are three different ways in which run code is interpreted:

• Linear: Each extra loop increases run time in the same way
• Exponential: Each extra loop increases run time exponentially, so many extra loops will drastically increase run time
• Logarithmic: Each extra loop increases run time logarithmically, so after one point extra loops have a minimal impact on run time

To calculate run time, we need to pay close look at our code in order to establish how many steps and loops are given. Let's look at this piece of code and its outcome:

    for i in range(l):

        print(i)

If we use l = 10, how many times will print() be used?

Print will be used 10 times. The output would be the following:

0

1

2

3

4

5

6

7

8

9

What about the number of steps? Would it be 10 steps? 

We need to consider that there are two steps involved: for and print(). In this case, we would be talking about 20 steps in total, one for for and one for print() per loop.

Now let's change the code a little bit:

    for i in range(l):

        print(i)

        for j in range(l):

            print(j)

If we use l = 10, how many times will print() be used?

Print will be used 10 times in the outer loop, and 10 times in the inner loop for each loop in the outer loop. This means that print will be used 10 * 10 = 100. The output would be the following:

0

0

1

2

3

4

5

6

7

8

9

1

0

1

2

3

4

5

6

7

8

9

2

0

1

2

3

4

5

6

7

8

9

3

0

1

2

3

4

5

6

7

8

9

4

0

1

2

3

4

5

6

7

8

9

5

0

1

2

3

4

5

6

7

8

9

6

0

1

2

3

4

5

6

7

8

9

7

0

1

2

3

4

5

6

7

8

9

8

0

1

2

3

4

5

6

7

8

9

9

0

1

2

3

4

5

6

7

8

9

What about the number of steps? Would it be 100 steps?

Similarly to the previous question, we need to consider both inner and outer loop, and their interaction. The inner loop has 2 steps, and the outer loop has 2 steps, and each time the outer loop runs, the inner loop runs l times. Hence, in this case, we are talking about 20 steps per each run of the inner loop, so it would be 200 steps of the inner loop with 20 steps of the outer loop. In total, 220 steps.

As we can see, proper analysis of the code needs to take place in order to decipher how the loops interact and, finally, how many steps will be taken.