Homework: Homework 1. Asymptotic Analysis

Assigned

• September 8, 2026

Due

• September 18, 2026 10:00pm

Collaboration

Make sure you review and understand the policies on the syllabus before you discuss your work on this assignment with anyone.

Submitting

You will submit your compiled pdf on Gradescope. Everything must be typed in \(\Latex\) If you are asked to design an algorithm, please provide: (a) the pseudocode or precise description in words of the algorithm, (b) an explanation of the intuition for the algorithm, (c) a proof of correctness, (d) the running time of your algorithm and (e) justification for your running time analysis.

1. CLRS 3.2-2 Explain why the statement, "The running time of Algorithm $A$ is at least $O(n^2)$" is meaningless

2. CLRS 3-1abc Asymptotic behavior of polynomials

3. CLRS 3-2 Do only the $O, \text{ } \Omega , \text{ and } \Theta$ columns

4. CLRS 3-4adfg 

5. CLRS 3-3 Order by asymptotic growth rates: ($g_1=\Omega(g_2)$) \(\begin{array}{llllll}\\ lg(lg^*n) & 2^{lg^*n} & (\sqrt{2})^{lg n} & n^2 & n! & (lg n)!\\ \frac{3}{2}^n & n^3 & lg^2n & lg(n!) & 2^{2^n}& n^{\frac{1}{lgn}}\\ lnln n & lg^* n & n\cdot 2^n & n^{lglgn} & ln n & 1\\ 2^{lgn} & (lg n)^{lg n} & e^n & 4^{lgn} & (n+1)! & \sqrt{lg n}\\ lg^*(lgn) & 2^{\sqrt{2lgn}} & n & 2^n & nlogn & 2^{2^{n+1}}\\ \end{array}\)