Algorithm analysis

Start of fall break. I will be trying to update a lot during the next few days as I work towards trying to catch up on material. Ever since the second midterm test (I got a 15/30), I've realized that I've fallen quite a lot behind on this work. So, during this fall break, I'll be trying my best to try to catch up. Talk about the procrastination bug striking. Man that really bites. :\

Today, on Saturday, I will be working towards learning how to count running time, and I'll document my progress as I try to figure this out.

Linear Search:

def ls (A,x):

1    i = 0

2   while i < len(a):

3        if A[i] == x:

4            return i

5        i = i+1

6    return -1

After tracing the program through a couple of times, I've figured out that the idea behind this was the following. Assume element x was found in position j. What we notice is that lines 1 will execute at least and at most once. We NEVER return back to it, so we have the running time of this program (denoted R(ls)) so far as 1. Then, we notice that lines 2,3, and 5 will execute if the element does not equal to the index. This contributes 3 but the question is how many times does it contribute 3? 

Do we contribute 3 once? Twice? Infinitely many? That was why I specifically stated that element x was found in position j. Indices 0,1,2,3,..., (j-1) will each contribute 3, because at those indices, the element is not found at that position. Thus, by our previous observation, this process will add 3 each time. But how many times? Well, how many elements are there from 0 to j-1? (j-1)-0+1 elements! Thus, our R(ls) is now updated to 1 + 3j.

What happens when the element is found? Let's take a look. Line 2 will execute because i will be less than the length of the list of a if the element exists in the list, so we add one to our R(ls). Now, R(ls) = 1 + 3j + 1. Then we check if A[j] == x, counting as one more step. R(ls) = 1 + 3j + 1 + 1 = 1 + 3j + 2. This check will yield true, because as we stated before, the item will be found at index j, so we execute the return statement j statement, yielding one last +1 to our R(ls), and ending the run time of this function.

Our final R(ls) is 1 + 3j + 3, so we're done.

BUT WAIT. This only covers if we do find the index. What if we don't find the index? Well, LET'S TRACE IT!

We go through line 1 again. only once. However, lines 2,3, and 5 to get run len(A) times, since we loop through the whole list, plus one more for the final i<len(a) check, and plus one for the return -1 statement.

Thus R(ls) if we don't find the item to be R(ls) = 1 + 3*len(a) + 2.

That'll be it for my post for today.