In this week, we learned about formal definition of O and big omega. The definition wasn't hard to understand. O(n) means a set of functions that grow no faster than n and only highest-order term matter. The definition of big omega(n) means the set of function that grow no slower than n. Therefore graph of O(n) is upper_bounded when graph of big-omega is lower bounded.
Furthermore, we learned about analyze a sorting algorithm and proving the worst case-complexity of insertion sort. Using insertion sort we proved the worst case upper bound by overestimating. At first I was confused by what we are doing. I started understanding everything and also being able to predict what the next step would be. I must read course notes again and re-read the lecture slides.
No comments:
Post a Comment