# CSE 373 Homework #2: Algorithm Analysis

\$30.00

## Description

1. (4 points) Show that the function log2(9N) is O(log2N). You will need to use the definition
of O(f(n)) to do this. In other words, find values for c and n0 such that the definition of BigOh holds true as we did with the examples in lecture. For full credit, show the steps you took
to arrive at your c and n0.
2. (6 points) (adapted from Weiss 2.1) Order the following functions by growth rate:
N2
, N log N, 2/N, 2N
, 92, N2 log N, N!, N1.5,
N3
, log N, N log (N2
), 4logN
, N
Indicate which functions grow at the same rate. Recall that a function f(N) grows at the same
rate as function g(N) if f(N) = Θ(g(N)).
3. (8 points) (from Weiss 2.2) You do not need to prove an item is true (just saying true is
enough for full credit), but you must give a counter example in order to demonstrate an item
is false if you want full credit. To give a counter example, give values for T1(N), T2(N), and
f(N) for which the statement is false.
Suppose T1(N) = O(f(N)) and T2(N) = O(f(N)). Which of the following are true?
a. T1(N) + T2(N) = O(f(N))
b. T1(N) – T2(N) = o(f(N))
c. T1(N) / T2(N) = O(1)
d. T1(N) = O(T2(N))
4. (10 points) (adapted from Weiss 2.7) Give the Big-Oh for each of the following code
excerpts. For parts (a) – (c), verify your Big-Oh doing a precise algorithm analysis, using
summations and reducing to closed forms as demonstrated in class. You may want to refer to
section 1.2.3 in the book for series formulas. For full credit, show your work of how you
used summations to reduce to closed form. For part (d), give a brief explanation as to how
you came up with your Big-Oh.
a)
sum = 0;