CS313E – Software Design

Assignment 4 – 100 Points

Tasks

1. Use python to create 3 different plots of the following functions (15 points):

f1(n) = (2

10)(n) + 2

10

f2(n) = n

(3.5) − 1000

f3(n) = 100n

(2.1) + 50

• Create 3 plots and limit the horizontal x-axis to n = 5, 15, 50. On each of the 3 plots you

need to show the above 3 functions. On the first plot the x-axis is limited to 5, on second

one x-axis is limited to 15 and on the 3rd one x-axis is limited to 50.

• Visualize the 3 functions in 3 colors (f1 in red, f2 in blue, f3 in green).

• Describe your visualization and what you see in these 3 plots.

• Add your visualization and your python code to your PDF report file.

You can use the template implementation provided in class.

2. Asymptotic Notation. (15 points)

• Is 2(n+1.3) = O(2

n) ?

• Is 3(2×n) = O(3

n)?

Describe your answer.

Page 1 of 2

3. For each pair of functions f (n) and g(n), check if f (n) = O(g(n)) ?

Functions f (n) and g(n) are:

1. f (n) = (4 × n)

150 + (2 × n + 1024)

400 vs. g(n) = 20 × n

400 + (n + 1024)

200

2. f (n) = n

1.4 × 4

n vs. g(n) = n

200 × 3.99n

3. f (n) = 2

log(n) vs. g(n) = n

1024

Describe your justifications. (30 points)

4. Analyze the Algorithm 1 and give a Big O bound on the running time as a function of n.

Carefully describe your justifications. (20 points)

Algorithm 1 What is the Big O of this pseudocode?

1: i = 1

2: while i ≤ n do

3: A[i] = i

4: i = i + 1

5: end while

6: for j ← 1 to n do

7: i = j

8: while i ≤ n do

9: A[i] = i

10: i = i + j

11: end while

12: end for

5. Analyze the Algorithm 2. What is the Big O on the running time as a function of n.

Carefully describe your justifications. (20 points)

Algorithm 2 What is the Big O of this pseudocode?

1: x = 0

2: for i ← 0 to n do

3: for j ← 0 to (i × n) do

4: x = x + 10

5: end for

6: end for

Page 2 of 2

CS329e - Elements of Software Design

# Software Design Assignment 4

Original price was: $35.00.$30.00Current price is: $30.00.

## Reviews

There are no reviews yet.