Big Omega and General Statements

    This week we wrapped up the Big O session with Big Omega proofs and general Big O statements. The Big Omega proofs are very similar to the Big O proofs. The way I remind myself is this: if I am trying to prove that g(n) <= c*f(n), I will have to manipulate g(n) into a similar expression, say g’(n), that is greater than g(n). This way if g’(n) <= c*f(n), the statement will be true. By the same logic, for f(n), I will have to find a f’(n) that is smaller. Every time I start a proof, I go through this process to see what I am trying to find. This extra process helps me a lot, since I will not have to memorize the steps and possibly get confused by Big O and Big Omega. In terms of general statements of the Big O, I find that it is crucial to understand the relationships between the variables and to utilize the definition of the Big O. This dictates what examples to pick when proving a statement (ie. max, multiplication).