I have always wondered what something like O(nlogn) meant after my brief foray into reading about sorting algorithms on Wikipedia. Now I know. O() is the notation for asymptotic upper bound. Efficiency is very important in computer programming. Computing time takes up money and resources. Asymptotic notation allows us to analyze the efficiency of functions.
When we say running time, we don't actually mean running time. We mean the the number of steps (lines of code) that need to be executed in order to run a function. With asymptotic upper bound, we focus on the worst case scenario. So if you are searching for an something in the list, the worst case scenario is when that thing does not appear in the list at all. This would require the largest number of lines to be run. As well with asymptotic notion, we do not care about constant terms, and only the highest order term matters. So everything from n^2 to n^2 + 3n + 4 to 109352543n^2 + n + 43243 all belong in O(n^2).
No comments:
Post a Comment