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.
