Growth of Functions
Recall the following results:
| Algorithm |
Asymptotic Running Time |
| Insertion Sort |
Q (n2) |
| Merge Sort |
Q (n lg n) |
Asymptotic Running time: As "n gets big" the running time scales like this, or the limit as n ® ¥
Warning: Asymptotic results may be hazardous to your health:
- They may hold only when n is "too big".
- For a particular n, the best asymptotic algorithm may not be the quickest -- in other words, what if n is not anywhere close to infinity.
|
