Week 10

So this week we got our second midterm back. I managed to get perfect once again so I am happy about that. In class this week, we looked at proving big O for non-polynomial functions. We used L'Hôpital's rule to help prove that 2^n was in big O of n^2. L'Hôpital's rule uses derivatives to evaluate limits and is defined as:

Two other bounds we talked about were big Omega and big theta. A function f is in big Omega of function g  (f(x) = Ω(g(x))) if it is bounded below by function g. A function f is in big theta of function g (f(x) = Θ(g(x))) if it is bounded both above and below by function g.

Another interesting thing I learned this week were some of the properties of big O.

The reflexivity property says that a function is in big O of itself, which makes sense since we can easily see that if we multiply a function by a constant, then the original function will always be less than the new function. Reflexivity also means that a function is in big Omega, as well as big theta of itself.

The transitivity property says that if function f is in big O of g and function g is in big O if h, then function f is in big O of h. We can prove this by choosing the constant to be the product of the two constants for the first two functions and the breakpoint to be the maximum of the two breakpoints for the first two functions.

That's it for this week. I have one midterm left for one of my courses and so far I have done well on them. After that it will be on to exams, something I am definitely looking forward to!