# Homework #1 Running Times Solution

\$30.00

Category:

## 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 !!