|
home—info—lectures—exams—archive
When showing that one function is big-Oh of another, use the definition of big-Oh and find specific constants c,k satisfying the definition of big-Oh1
problem size | bit operations needed | ||||
problem size: n |
log n | n | n² | n3 | 2n |
10 | |||||
100 | |||||
1000 | |||||
106 (million) | |||||
109 (billion) |
Aside: This problem is interesting because Rosen shows that the greedy algorithm is optimal when nickels are included, but now we see that in other situations the greedy algorithm isn't optimal. Rosen's proof is not as 'obvious' as it might seem, since it depends on nickels in some crucial way.
Aside, continued: Mathemeticians immediately start to wonder: When considering different types of coins, what conditions are sufficient to guarantee that the greedy algorithm will work? What conditions are necessary, to guarantee this?
1 In class I used n0 instead of Rosen's k. ↩
home—info—lectures—exams—archive
©2008, Ian Barland, Radford University Last modified 2008.Dec.15 (Mon) |
Please mail any suggestions (incl. typos, broken links) to ibarlandradford.edu |