This week we started big O and big theta. I have learned big O in high school, but not this specific. What we did was given a block of code, we had to find out its average case efficiency. We only had more general answers like 1, log(n), n, n^2, 2^n because we only cared the highest degree. However, in this course we have to find everything. The definition of over and underestimate are really abstract and complicated in terms of symbols; however, when I put them in simple English, they are much more comprehensible.
I feel like overestimate is easier to do than underestimate because it's easier to assume for the worst. When overestimating the insertion sort algorithm, all we had to do was to assume every while loop will run n time and one loop guard. However, we had to add an arithmetic sequence (from 1 to n-1) when evaluating the nested loop when we were doing an underestimate. Is it easier to assume the worst of the worst than the best of the worst?
No comments:
Post a Comment