Big oh of non-polynomial functions.

I'm back! And today, we're going to be talking about how to apply calculus to solve big-oh notation type questions.

So, how would we prove that n is in O(2^n)?

Let's take a graphical look:

http://gyazo.com/50b4f15c85b4a932c322fb648be480d5

It seems that as x grows larger and larger, 2^x "overpowers" the rate of growth of n. So how can we formalize this "overpowering" factor? The way to do this comes from calculus. If 2^x grows much faster than x, then as x gets arbitrary large, 2^x/x would also get arbitrary large. So in calculus terms, the limit as x-> infinity of (2^x/x) must be infinity.

But that was just intuition, we need a proper definition of limit as x -> infinity of some f(x) = infinity, which would be: For all e in positive reals, there exists an n0 in naturals such that for every n in naturals greater than or equal to n0 would imply that 2n/n > e.

Side note: if the limit does exist for some f(x) (in other words the limit as x -> infinity of some f(x) = c), then the definition would be that for all e in positive reals, there exists an n0 in naturals such that for every n in naturals greater than or equal to n0 would imply that c-e<2n/n <c + e.

While this may seem wordy, it's just saying that as x gets arbitrarily large, it either grows without bounds, or that it is bounded.

So how does this help us solve something like n is in O(2^n)?

Well, we know that limit x -> infinity of n/2^n = 0.

Filling in our regular parameters for the definition of big-oh notation, which I remind you in the following.

g(n) is in O(f(n)) when:

There exists c in positive reals, there exists B in naturals such that for all natural n >= B => g(n) <= cf(n).

So here is the following proof for n in 2^n:

Assume B = 1, and c = 1.

Since we know that the limit is infinity, we can set e to be whatever we want, so I chose e = c.

Then there exists an n0 such that for every n >= n0 => n/2^n < 1
Let n0 be such that for every natural n >= n0 => 2^n/n > 1, and n' = max (B,n0) # I'll explain why we use the B later.
Then n' is in naturals, since it's either B, a natural, or n0, a natural.
Then n' >= B. This is why we use max (B,n0), so that we can satisfy the breakpoint condition of the original problem. If we didn't include B, then how would we know that n' >= B?
Then n < c*2^n, since n >0.
Then n' >= B and n' < 2^n'  #since c = 1
Then there exists an n in naturals such that n >= B and g(n') < cf(n')
Then there exists c in positive real, there exists B in natural, for all n in natural, such that if n is greater than or equal to B then n <= c2^n

EDIT:

It's come to my attention that recently a lot of people (judging from the SLOGS) are having trouble with this idea of limits. Simply put, the idea is that at infinity, which one increases faster: f(x) or g(x) in f(x)/g(x)? If f(x), then the limit goes to infinity. If g(x), then the limit goes to 0. It's as simple as that.

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.

Exam feedback + Assignment #1

Exam feedback is here! Did pretty well for my expectations with 34/35. Couldn't expect anything better out of that.

The following weeks, CSC165 focused on proofs and and introduction to Big-Oh notation, as well as assignment one went down.

For assignment one, I felt that we did pretty well regarding the logic ideas. I learned a lot through boolean algebra back in high school, so coming here and adapting to formal mathematical language was kind of easy for me. I felt what was truly confusing for the assignment 1 was how to draw venn diagrams for question 3. In a sense, it really tested your understanding of what these sentences mean in terms of where items can or cannot belong to.

For proofs, the hardest thing I had trouble with was the idea of floor. It never really clicked with me how the second part of the floor part described how it was the biggest integer. Perhaps someone can explain to me?