# 演算法作業二

###### tags: `演算法`

1. Indicate, for each pair of expressions (A, B) in the table below, whether A is O, o, Ω, w, or Θ of B. Assume that k ≥ 1, ε > 0, and c >1 are constants. Your answer should be in the form of the table with “yes” or “no” written in each box.

基本原則:
每一題皆先求$\lim_{n\rightarrow \inf}\cfrac{A(n)}
{B(n)}$
如果趨近0，代表小o成立，也代表大O成立
趨近無窮大，代表w成立，也代表$\Omega$成立
如果是一個整數，代表$\theta$成立，也代表大O跟$\Omega$成立

如果有無法用上述方法的情況則自行判斷

2. Given two non-negative function $f, g$ (i.e. $f, g$ : $N → R^*$) such that $f≠O(g)$, $f≠θ(g)$, and $f≠Ω(g)$.

Answer:
我們的目標是找到$\lim_{n\rightarrow \inf}\cfrac{f(n)}
{g(n)} != \inf$ 然後同時diverge

$f(n)=n^{1/2}$
$g(n)=n^{\sin(n)}$

3.

4. Let f(n) and g(n) be asymptotically positive functions. Prove or disprove each of the following conjectures.
a. $f(n) = O(g(n))$ implies $g(n) = O(f(n))$.
b. $f(n) + g(n) = Ѳ(min( f(n), g(n))$.
c. $f(n) = O(g(n))$ implies $lg(f(n)) = O(lg(g(n)))$, where $lg(g(n)) ≥ 1$ and $f(n) ≥ 1$ for all

Answer:

d. $f(n) = O(g(n))$ implies $2^{f(n)}= O(2^{g(n)})$.
e. $f(n) = O((f(n))^2)$.
f. $f(n) = O(g(n))$ implies $g(n)= Ω(f(n))$.


g. $f(n) = Ѳ(f(n/2))$.
h. $f(n) + o(f(n)) = Ѳ(f(n))$. (錯了 答案是prove)
i. $f(n) = Ѳ(g(n))$ implies $f(n)/g(n)=c≠0$


5. Solve the recurrence $T (n) = 2T (√𝑛) +1$ by making a change of variables. Your solution should be asymptotically tight. Do not worry about whether values are integral.

Answer:

6. Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for n≦2. Make your bounds as tight as possible, and justify your answers.

Answer: Solve them by master theorem
a. $T(n)=2T(n/2)+n^3$

b. $T(n)=T(9n/10)+n$