last updated 1/7/08
These exercises are borrowed from Headington/Riley, Data Abstraction and Structures Using C++, DC Heath, 1994.
Below are pairs of cost/time functions. Determine the best big-Oh and which of the pair dominates or neither.
| Functions | Domination: T1 or T2 or neither | big-Oh | |
|---|---|---|---|
| a. | T1(X) = 2*X2 T2(X) = 2*X |
||
| b. | T1(X) = 5*X2 T2(X) = 2*X3 |
||
| c. | T1(Y) = 55*Y15+3*Y4+7500 T2(Y) = Y16+2 |
||
| d. | T1(Z) = (Z+3)(Z+9) T2(Z) = 250*Z |
||
| e. | T1(Z) = (Z+7)(Z+5) T2(Z) = 2*Z3 |
||
| f. | T1(N) = 37*N2 T2(N) = N log N |
||
| g. | T1(N) = 37*N2 T2(N) = N2 log N |
||
| h. | T1(N) = log2N T2(N) = log3N |
||
| i. | T1(N) = 84 T2(N) = log9N |
||
| j. | T1(X) = (3*X+2)/X T2(X) = 766*X |
||
| k. | T1(X) = (X4+X2-17)/X3 T2(X) = X2 |
||
| l. | T1(W) = W9 T2(W) = 9W |
||
| m. | T1(W) = W! T2(W) = 67W |
||
| n. | T1(V) = VV T2(V) = 25V |
||
| o. | T1(N) = 55*N3+77*N2+99 T2(N) = 2N+N2 |
||
| p. | T1(N) = 3N+N2 T2(N) = 2N*N2 |
||
| q. | T1(N) = (N log N)/(2+N) T2(N) = log N + 46*N |
Rank the following big-O measures from least to greatest. Name them (constant, linear, quadratic, cubic, logarithmic, polynomial, factorial and exponential)
| Rank | Name | |
|---|---|---|
| O(N) | ||
| O(N!) | ||
| O(4N) | ||
| O(log4N) | ||
| O(log3N) | ||
| O(N2) | ||
| O(1) | ||
| O(N log2 N) | ||
| O(N2 log2 N) | ||
| O(N3) |