# HW1: Due Jan 26th, Before Midnight (i.e., by 11:59:59PM on 26th)

To solve these problems, you are allowed to consult your classmates, as well as the class textbook (Algorithms by Dasgupta, Papadimitriou, and Vazirani, which we will call DPV) and notes, but no other sources. We encourage you to collaborate with other students, while respecting the collaboration policy. Please write the names of all the other students you collaborated with on the homework. Everyone must write up their assignments separately.

Q1. (20 points; 10 per part) DPV Problem 0.3 (parts a and c)

Q2. (10 points) Consider the following pseudo-code which takes the integer $$n \ge 0$$ as input:

Function bar(n)
Print '*';
if n == 0 then
Return;
end
for i = 0 to n − 1 do
bar(i);
end


Let T(n) be the number of times the above function prints a star (*) when called with input n ≥ 0. What is T(n) exactly, in terms of only n (and not values like T(n − 1) or T(n − 2))? Prove your statement.

Q3. (30 points; 5 per part) For each of the following pairs of functions, indicate whether the first function is $$O, \Omega, \Theta$$ of the second function:
a. $$n(n + 1)$$ and $$2000n^2$$
b. $$100 n^2$$ and $$0.01 n^3$$
c. $$\log_2 n$$ and $$\ln n$$
d. $$\log_2^2 n$$ and $$\log_2 n^2$$. Note that $$\log_2^2 n = (\log_2 n)^2$$
e. $$2^{n−1}$$ and $$2^n$$
f. $$(n − 1)!$$ and $$n!$$

Q4. (10 points) Order the following functions by their order of growth from the lowest to the highest:
$$(n − 2)!$$, $$5 \log_2(n + 100)^{10}$$, $$2^{2n}$$, $$0.001 n^4 + 3n^3 + 1$$, $$\ln^2 n$$, $$(n)^{1/3}$$, $$3^n$$

## How to submit:

Your HW must be submitted in PDF Format only. If you submit any other type of document, points will be deducted from your overall HW score. As noted above, you must mention upfront all students you collaborated with, but all final work must be your own.

You should submit the PDF file via the Submitty page: https://submitty.cs.rpi.edu//index.php?semester=s18&course=csci2300