Answers to Homework # 2

 

  1. a)  f(n) = n2 + 2n + 6 = O(n2)

 

      yes.  choose c = 9, n0 = 2    and note that 2n < 2n2  and 6 < 6n2  for n >= 2

 

      b)  n2  = O (n3)

      yes.  choose c = 1, n0 = 2  and show n2 <= n3  for all n >= 2.  Divide both sides of

      inequality by n2 and we have 1 <= n for all n >= 2.

 

      c) 2n+1 = O(2n)

      yes choose c = 2, n0 = 1 and apply definition.

 

      d) n! = Q((n+1)!)

      false can show that n! <= (n+1)! for all n >= 1,  but there is no choice of c, n0 pair

      such that (n+1)! <= c n! for all n >= n0

 

  1. Order of functions according to increasing asymptotic behavior.

      Ön Í n lg(n) Í n1+e Í n2/lg(n) Í (n2 - n + 1) Í n8 Í (1 + e)n Í  2n = 2n+1 Í  n!

      Í  (n+1)!  Í nn

 

  1. f(n) = n2 days                g(n) = n3 sec

      1 day = 24 x 60 x 60 = 8.64 x 104 sec

      f(n) = 8.64 x 104 n2 sec             f(n) = g(n) when 8.64 x 104 n2 = n3

      g(n) >= f(n) for problems of size n = 8.64 x 104

      problems of size n = 8.64 x 104 require n3 seconds to solve  n3 >= (8.64 x 104)3

      f(n) <= g(n) after about 6.45 x 1014 sec.  and 6.54 x 1014 sec/p x 107 sec/year = 2 x 107 years

      f(n) outperforms g(n) after 20 million years.

 

  1. f(n) = n2 days                g(n) = 2n seconds

      again, set (8.64 x 104 sec/day) n2 days = 2n seconds

      take the log of both sides

 

      log(8.64) + 4 log(10) + 2 log (n) = n log(2)

 

      0.93 + 4 + 2 n = 0.301 n

 

      by trial and error choose n= 25  and plug into above equation -- both sides about the same.

      before f(n) outperforms g(n) on problems of size n >= 25, requires computations lasting

      n2 days or about 625 days (almost 2 years)

 

  1. Answer to problem 5 -- see table below

            Fill in the table to determine the size of the problem that can be run for each table entry. 

     

 

 

1 sec

1 min

1 hour

1 day

1 year

1 century

 

lg(n)

 

 

210**6

 

26 x 10**7 

 

23 x 10**9

 

28 x 10**10

 

2p x 10**13

 

2p x 10**15  

 

n

 

 

   106    

 

6 x 107 

 

3.6 x 109  

 

 8.64 x 1010

 

p x 1013     

 

 p x 1015       

 

nlg(n)

 

 

6 x 104

 

 

 

 

 

1012

 

~1015

 

n2

 

 

103

 

 8 x 103    

 

6 x 104

 

3 x 105

 

5.6 x 106

 

5.6 x 107

 

n3

 

 

 102      

 

4 x 102

 

1.5 x 103    

 

4.5 x 103    

 

1.3 x 104 

 

1.5 x 105   

 

2n

 

 

20

 

25.8

 

31.8

 

36.5

 

44.3

 

51

 

n!

 

 

9

 

11

 

12

 

14

 

16

 

17

 

 

Sample Calculations

 

1 sec = 106 ms                   

 

      lg(n) = 106        ßà  n = 210**6                where 10**6 = 106

 

      2n = 106           ßà n log10(2) = 6       0.301 (n) = 6      n = 20

 

      use trial and error to find n! » 106          and    n lg(n) = 106