Linear Searching

In this slog we shall talk about counting steps and worst case scenarios for Big-Oh. This is the topic in which we have to actually understand how each line in python works. This particular topic was quite difficult for me to understand in the lectures. I had trouble grasping the concept of which lines have to be executed one after the next. However, Madina, my TA, made it a bit easier for me to understand this particular topic.

We were presented with this question for the quiz.

This was the code given to us for sum_up

   

def sum_up (n): 

    i = 0

    s = 0

    while i < n:

        j = i

        while j>= 0:

            s = s + 1

            j = j - 1

        i = i + 1

    return s

At first I had no idea really how to start with this question. However, I tried to remember the steps Madina showed us in how to read and understand each line. The first question was, what do sum_up(0), sum_up(1) and sum_up(2) return?

For sum_up (0), it returns 0

For sum_up (1), it returns 1

For sum_up (2), it returns 3

The general expression for what sum_up (n) returns is (n (n+1))/2

We were required to write steps to explain our thinking.

The outer while loop iterates i < n for the values i = 0 …..n = n-1 and the inner while loop iterates for values j = i ……0. Thereby, s would keep going through the sums on each of the iterations once it is satisfied.

Therefore n-1

                   Σ     (i  + 1) = (n(n + 1))/2

               i < n
I have also browsed through many different slogs in which I though all of them were so unique filled with so many great ideas, creativity and interpretations in problem solving for this course. However, I found one that stood out impeccably for me. Take a look!

http://www.soohamrafizslog165.blogspot.ca/