CSC165 sLOG 9

  As I have already say goodbye to test 2 and chapter 3, I have no reason not to pay more attention on chapter4 regarding algorithm analysis and asymptotic notation. In lecture, pro introduced the upper bound and lower bound for the input with the size of n in worst case. Then he provided us some examples about Wis belongs to big Oh. f(n) belongs to O(g(n)) means there exists a real number c and a natural number B for every natural number n, if n is no less than B, then f(n)less or equal to c times g(n). c is a multiplier ,B is a breakpoint, so that you can go far enough to the right the function is bounded above by cg(n). In terms of limits, this says that as n approaches infinity, f(n) is less than cg(n) once you find the appropriate c.At the beginning, I found the big Oh problem is not easy to do. But after some practices in lectures and tutorials, I become more and more familiar with these kind of problems. It also requires you to be good at writing proof structure. By the way, it is important to remember that for every while loop, we need to execute one more step for the first line!
   Regarding polynomials for big Oh problem, f belongs to O(g) when the highest-degree term of g is no smaller than the highest -degree term of f. Furthermore, logarithmic functions are in big Oh of any polynomials, whereas exponential functions are not in big Oh of any polynomials.When proving some big oh questions regarding exponential functions, it is useful to use the meaning of limit. We also learnt big Omega problems, which is the opposite to big Oh by definition. This time the role of c is to scale g down to below f.