CMSC 435 Algorithm Analysis and Design
Homework Assignment # 2
Due Monday, September 14
1. Which of the following statements are true? Prove your answers.
a) n2 + 2n + 6 Î O(n2)
b) n2 Î O(n3)
c) 2n+1 Î O(2n)
d) n! Î Q((n+1)!)
2. To illustrate how asymptotic notation can be used to rank the efficiency of algorithms, use the relations “Ì”
and “=” to put the orders of the following functions into a sequence, where e is an arbitrary real constant, 0 <e <1.
n lg n n8 n1 + e (1+e)n n2/lg n (n2 - n + 1)
n! (n + 1)! 2n 2n + 1 nn nlg n Ön
3. Two problems take n2 days and n3 seconds respectively to solve on an instance of size n. Show that it is only on instances requiring more than 20 million years (1 year = p x 107 seconds) that the quadratic algorithm outperforms the cubic algorithm.
4. Two algorithms take n2 days and 2n seconds respectively to solve an instance of size n. What is the smallest instance on which the former algorithm outperforms the latter? Approximately how long does such an instance take to solve?
5. In the table below, you are given the run-time cost of a number of algorithms (rows) and the time each algorithm is allowed to run (columns). Assume that a single instance of each problem can be run in 1 microsecond (10-6 seconds). Fill in the table to determine the size of the problem that can be run for each table entry. (I have filled in a couple of entries to get you started.)
| 1 sec | 1 min | 1 hr. | 1 day | 1 year | 1 century |
_____ |_____ |_____ |_____ |_____ |_____ |________|
lg(n) | | | | | | |
_____ |_____ |_____ |_____ |_____ |_____ |________|
n | 106 | | | | | |
_____ |_____ |_____ |_____ |_____ |_____ |________|
nlg(n) | | | | | | |
_____ |_____ |_____ |_____ |_____ |_____ |________|
n2 | 103 | | | | | |
_____ |_____ |_____ |_____ |_____ |_____ |________|
n3 | | | | | | |
_____ |_____ |_____ |_____ |_____ |_____ |________|
2n | | | | | | |
_____ |_____ |_____ |_____ |_____ |_____ |________|
n! | | | | | | |
_____ |_____ |_____ |_____ |_____ |_____ |________|