**NAME: _________________________________________________**

- Show that 3n
^{3}+ n^{2}is big-Oh of n^{3}. You can use either the definition of big-Oh (formal) or the limit approach.**Show your work!**(5 pts.)

- An algorithm takes 0.5 ms for input size 100. How long will it take for input size 500 if the running time is the following? (hint:
*see Running Time Estimation in notes on Algorithm Analysis*)

**Show your work!**(20 pts.)

linear

b. O(NlogN)

c. quadratic

d. cubic

- An algorithm takes 0.5 ms for input size 100. How large a problem can be solved in 1 min if the running time is the following? (hint:
*see Maximum Problem Size in notes on Algorithm Analysis*)

**Show your work!**(15 pts.)

linear

b. quadratic

c. cubic

- Consider the following algorithm:

int j = 1;

int k = 1;

for (i = 1; i <= 10; i++)

j = j * 100; ß consider this a basic operation

for (i = 1; i <= 20; i++)

k = k * 2; ß consider this a basic operation

What is the running time, T(n)? Give both the exact function T(n), and then give a big- Theta estimate of T(n). Show your work. For example, if T(n) is exactly n^{2} + 3n, then T(n) is big-Theta of n^{2}. **Show your work!** (10 pts.)

- Consider the following algorithm:

sum = 0;

for ( i = 0; i < n; i++ )

for ( j = 0; j < i * i ; j++ )

for ( k = 0; k < j ; k++ )

sum++;

What is the general running time, T(n)? Give a big- Theta estimate of T(n). **Show your work!** (10 pts.)

- If
**f(n)**is big-theta of**g(n)**, then the value of**f**may be infinitely away from that of**g**. (True or False) Explain! (5 pts.)

- If the worst case time of algorithm A is big-oh of that of B, then B is
faster than A for large problems. (True or False) Explain! (5 pts.)__never__

- Hardware vendor XYZ Corp. claims that their latest computer will run 100 times faster than that of their competitor, Prunes, Inc. If the Prunes, Inc. computer can execute a program on input of size n in one hour, what size input can XYZ’s computer execute in one hour for each algorithm with the following growth rate equations? (10 pts.)
**Show your work!**- 2/N
- Log N

: On the Sorting Algorithms Animations site (__Bonus__*see Sorts folder in Course Content*), the QuickSort3 sort consistently performed better than standard QuickSort.how QuickSort is modified in QuickSort3 to deliver greater performance?__Explain__

**Note**:*Click the Sort name under the Algorithms heading for detail on each sort*. (10 pts.)