CSC165 Counting steps, worst-case, formal big-Oh

Week #8

Topic: counting steps, worst-case, formal big-Oh

The concept of big-Oh is very abstract, but I realized a few things that were really helpful to understand it. I would like to share some of them here.

Working with while loops

A while loop is a loop of the following form:

i = 1    # starting position

while (condition) : # when condition is true the loop executes

            body # The expressions to be repeated

            i += 1 # Increment of the loop

When working with big-Oh problems, we focus our attention on the condition. Let’s try a few examples:

1) Condition:  i  <  len(A). In this case, the loop will execute len(A) – 1 times

2) Condition:  i  <= len(A). In this case, the loop will execute len(A) times

The same works for i > len(A) and  i  >= len(A) when we are talking about a decrement, instead of an increment.

Nested Loops

a =  [[1, 2], [2, 3]]

1          i = 0

2          while i < len(a):

3                      j = 0

4                      while  j < len(a[i]):

5                                  print(a[i][j]|)

6                                  j += 1

7                      i += 1 # Increment of the loop

In this case, line 1 executes one time, line 2 executes len(a) +1 times, lines 3 and 7 execute

len(a) times, lines 5 and 6 execute (len(a) – 1)(len(a)) times because i and j start at 0, and line 4 executes (len(a))(len(a)+1) times.

This looks tricky at the beginning but the rule is that for any condition, we have to take the starting point (0), and subtract it from the first value that makes the condition false (len(a)). The result of this subtraction is going to be the number of times the code within the loop executes. As for the line with the while statement, this line executes one more time because it checks for the last possible value (len(a)).

I found this way and especially this example easier to understand, so I took them then as my starting point, and from there I was able to understand the concept of big Oh.