Week 10 - That GPA getting limited.

    After two weeks of dreadful weeks of Big Oh's,  the nightmare continues. This week starts off by continuing on the negations of the Big oh.  The problems were not to tackle since they are always based on polynomials. As result, simply by checking the biggest power on the variable in a polynomial, will lead one to the right path in proofing; rather than spending precious time in thinking whether to prove or disprove.

    
For instance, 

    
                          claim:     n^3 not in O(3n^2) 

    

    From first glance, it is obvious that n^3 will not be bounded by 3n^2 since it is obvious that n^3 will grow much quicker than n^2, and the 3 multiplier can be ignore as it will not matter too much as the numbers grows toward infinity.  

    
    To prove the claim, simply prove the negation of that n^3 is in big O of 3n^2 by choosing a breakpoint, by which n^3 will grows bigger than 3n^2.

    Through the weeks,  a new problem was introduced. The problem abruptly increases the complexity in proving Big oh. The problem is to prove a claim that compares two functions that is beyond polynomials. Therefore, it includes other functions like 2^n. 
     Well, for each new enemy, there is always a new weapon. Time to bring out the new weapon: the limit technique. The mechanics allow me to tackle the enemy in a completely new way. 
     
Taking this claim as an example:
                                 
                                     2^n is not in O(n^2)
    

    To approach the problem, I first express the claim as an limit that as n goes to infinity 2^n/ n^2. By using L.Hopital's rule, The limit evaluates to infinity. Then I am safe to state that if I choose an nc to defeat the c that the enemy hands me and defeat the problem.
     In addition to the week, I struggled upon the introduction of Big Omega. It differs only letter from Big oh as it allows me to choose a breakpoint -B- in which allow the claim to be true. However, that big difference took a way a large chunk of time. To fully understand the concept of the Big omega and its difference with Big oh, I used graphing calculators to interpret different graphs. It definitely helped as I can visualize the easier function and understand how Big omega is applied to it.