NYU CS-UY 1134 Lab3

Vitamins (30 minutes)

For big-O proof, show that there exists constants c, and $n_0$ such that $f(n) ≤ c*g(n)$ for every $n ≥ n_0$, then $f(n) = O(g(n))$.

For big-Θ proof, show that there exists constants $c_1$, $c_2$, and $n_0$ such that $c1*g(n) ≤ f(n) ≤ c2*g(n)$ for every $n ≥ n_0$, then $f(n) = Θ(g(n))$.

1. Use the **formal proof of big-O and big-**Θ in order to show the following (10 minutes):

a) $𝑛^2 + 5𝑛 − 2$ is $𝑂(𝑛^2)$

b) $\frac{n^2-1}{n+1}$ is $O(n)$

C) $\sqrt{5n^2 - 3n + 2}$

2. State True or False and explain why for the following (10 minutes):

a) $8n^2(\sqrt{n})$ is $O(n^3)$

b) $8𝑛^2(\sqrt{𝑛})$ is $Θ(𝑛^3)$

3. Sort the following 18 functions in an increasing asymptotic order and $write < or <= between$ each two subsequent functions to indicate if the first is asymptotically less than or asymptotically equivalent to the second function respectively.

For example, if you were to sort:

$𝑓_1(𝑛) = 𝑛$, $𝑓_2(𝑛) = 𝑙𝑜𝑔(𝑛)$, $𝑓_3(𝑛) = 3𝑛$, $𝑓_4(𝑛) = 𝑛^2$,

your answer could be $𝑙𝑜𝑔(𝑛) < ( 𝑛 <= 3𝑛) < 𝑛^2$

Hint: Try grouping the functions like so: linear, quadratic, cubic, exponential ... etc

$𝑓_1(𝑛) = 𝑛$

$𝑓_2(𝑛) = 500𝑛$

$𝑓_3(𝑛) = \sqrt{𝑛}$

$𝑓_4(𝑛) = 𝑙𝑜𝑔(\sqrt{𝑛})$

$𝑓_5(𝑛) = \sqrt{𝑙𝑜𝑔(𝑛)}$

$𝑓_6(𝑛) = 1$

$𝑓_7(𝑛) = 3^𝑛$

$𝑓_8(𝑛) = 𝑛 · 𝑙𝑜𝑔(𝑛)$

$𝑓_9(𝑛) = \frac{n}{log(n)}$

$𝑓_{10}(𝑛) = 700$

$𝑓_{11}(𝑛) = 𝑙𝑜𝑔(𝑛)$

$𝑓_{12}(𝑛) = \sqrt{9n}$

$𝑓_{13}(𝑛) = 2^𝑛$

$𝑓_{14}(𝑛) = 𝑛^2$

$𝑓_{15}(𝑛) = n^3$

$𝑓_{16}(𝑛) = \frac{n}{3}$

$𝑓_{17}(𝑛) = \sqrt{n^3}$

$𝑓_{18}(𝑛) = 𝑛!$

1. 常数函数：显然，对于足够大的n，任何常数函数都比对数、线性、多项式、指数函数小：

   • $𝑓_6(𝑛) = 1$
   • $𝑓_{10}(𝑛) = 700$

2. 对数函数：当n增大时，对数函数的增长率低于线性函数，但高于常数函数。其中，$𝑙𝑜𝑔(\sqrt{𝑛})$实质上是$\frac{1}{2}𝑙𝑜𝑔(𝑛)$，因此增长更慢：

   • $𝑓_4(𝑛) = 𝑙𝑜𝑔(\sqrt{𝑛}) = \frac{1}{2} log(n)$
   • $𝑓_{11}(𝑛) = 𝑙𝑜𝑔(𝑛)$

   同时，$\sqrt{𝑙𝑜𝑔(𝑛)}$随着n的增长而增长，但速度慢于直接的log(n)：

   • $𝑓_5(𝑛) = \sqrt{𝑙𝑜𝑔(𝑛)}$

3. 线性函数：这些函数与n成正比。显然，$𝑛$和$500𝑛$的增长速度比$\frac{n}{3}$要快：

   • $𝑓_{16}(𝑛) = \frac{n}{3}$
   • $𝑓_1(𝑛) = 𝑛$
   • $𝑓_2(𝑛) = 500𝑛$

4. 线性对数函数：$𝑛 · 𝑙𝑜𝑔(𝑛)$，它的增长速度介于线性和多项式之间：

   • $𝑓_8(𝑛) = 𝑛 · 𝑙𝑜𝑔(𝑛)$

5. 分数线性函数：随着n的增长，分母$log(n)$增加，使得整体函数的增长减慢，但它仍然比纯线性函数增长得快：

   • $𝑓_9(𝑛) = \frac{n}{log(n)}$

6. 平方根函数：这类函数的增长比线性慢，但比对数快：

   • $𝑓_3(𝑛) = \sqrt{𝑛}$
   • $𝑓_{12}(𝑛) = \sqrt{9n} = 3\sqrt{n}$

7. 平方函数：明显比线性和平方根函数增长得快：

   • $𝑓_{14}(𝑛) = 𝑛^2$

8. 立方根和立方函数：

   • $𝑓_{17}(𝑛) = \sqrt{n^3} = n^\frac{2}{3}$，它的增长比$n^2$慢，但比$n$快。
   • $𝑓_{15}(𝑛) = n^3$，显然，它的增长速度是所有多项式函数中最快的。

9. 指数函数：显然，$3^𝑛$的增长速度比$2^𝑛$快，它们都明显比多项式函数快：

   • $𝑓_{13}(𝑛) = 2^𝑛$
   • $𝑓_7(𝑛) = 3^𝑛$

10. 阶乘函数：增长最快。

    • $𝑓_{18}(𝑛) = 𝑛!$

整合上述分析，我们得到的排序为：
$𝑓_6(𝑛) \leq 𝑓_{10}(𝑛) \leq 𝑓_4(𝑛) \leq 𝑓_{11}(𝑛) \leq 𝑓_5(𝑛) \leq 𝑓_{16}(𝑛) \leq 𝑓_1(𝑛) \leq 𝑓_2(𝑛) \leq 𝑓_3(𝑛) \leq 𝑓_{12}(𝑛) \leq 𝑓_9(𝑛) \leq 𝑓_8(𝑛) \leq 𝑓_{14}(𝑛) \leq 𝑓_{17}(𝑛) \leq 𝑓_{15}(𝑛) \leq 𝑓_{13}(𝑛) \leq 𝑓_7(𝑛) \leq 𝑓_{18}(𝑛)$

4. Given the generator function, write the output: (10 minutes)

知识补充

公众号：AI悦创【二维码】