Slog for week 8

For this week, the professor Larry Zhang explained the formal definitions of  O and big omega and analyses of two algorithms. Since O and big omega are the concepts he explained last week, the definition was easy to understand: O(n) means the set of function that grows no faster than n, big omega(n) means the set of function that grows no slower than n. Therefore when we look at the graphs of f(n), then the graph of O(n) is upper-bounded while big omega(n) is lower-bounded.

Moreover, the second half of the lecture was about analyze a sorting algorithm, and proving the worst case of insertion sort. The professor divided the python function into three parts, then counted the number of steps needed in order to run the function. And this number of steps are written as sigma notation: this part was surprising because I never expected python function can be represented to sigma notation form.

But the part of picking the reasonable values is still pretty hard, and also determining whether the statement is true or not is hard. I know it can be solved if I solve the many questions as possible so that get familiar to the various kinds of questions.