Homework #1 Running Times Solution

$30.00

Description

1. Show that (log n) is a reasonable notation by showing that for every base b > 1,

log b n = (log 2 n):

n

i15 = (n16).

2. Show that Pi=1

  1. Show that n! = O(nn) but that nn 6= (n!).

  1. Show that the Fibonacci numbers grow exponentially.

  1. Plot the following 3 types of functions on the following 2 types of plots:

    1. An exponential function ( like 2n)

    2. A polynomial function ( like 10n2 )

    1. A bounded function (like 10 + sin n)

  1. a semi-log plot (X=linear scale, Y=logarithmic scale)

  1. a log{log plot (X=logarithmic scale, Y=logarithmic scale)

Which types of functions give STRAIGHT LINES in which types of PLOTS?

6. Plot the following empirical data values:

Input Size ( rst row)

Execution Time (second row)

12

13

14

15

16

17

18

19

20

21

22

23

24

0.028

0.055

0.109

0.165

0.330

0.660

1.32

2.58

5.05

10.2

20.3

40.7

81.4

What is the best kind of graph to use for this data set and why?

What would you guess the complexity of this function is and why? (for instance: linear, polynomial, exponential, etc.)

  1. What is the following algorithm computing?

Choose an inductive variable and state an inductive hypothesis you would use to prove that this algorithm does the job you claim it does.

WHILE B

>

0

Subtract

1

from

B

Add

1

to

A

ENDWHILE

  1. Use the data in the following table to decide if the run time has the form (2n). Use this data to predict the run time for n = 30.

n

Time (ms)

T (n)=T (n 1)

5

10

6

30

3

7

230

7.7

8

250

1.1

9

1287

5.1

10

1810

1.4

11

4270

2.4

12

10471

2.5

13

19398

1.9

14

39447

2.0

15

77669

2.0

16

147832

1.9

17

301652

2.0

Run Times for Prog-A and Prog-B as functions of n

n

Prog-A Time (ms)

n

Prog-B Time (ms)

2

0

2

0

4

0

4

0

8

0

8

0

16

0

16

0

32

0

32

15

64

0

64

31

128

15

128

78

256

31

256

218

512

140

512

625

1024

500

1024

1875

2048

2000

2048

5578

4096

8000

4096

16812

8192

32000

8192

50438

16384

128094

16384

151578

32768

512376

32768

454734

  1. Use the data in the above table for Prog-A and Prog-B. Plot this data and decide if the run times can be reasonably be written in the form ( nk ). Use you plot to estimate a kA for Prog-A and a kB for Prog-B. Which program do you expect to be asymptotically faster?

Important note from the grader: Besides getting the \right answers”, you will want to make sure your work is neat and clear. When doing graphs, for example, this means:

labeling your graph with a title or description, labeling and numbering your axes, and

choosing appropriate aspect ratios.


error: Content is protected !!