---
# System prepended metadata

title: 演算法作業二
tags: [演算法]

---

# 演算法作業二

###### 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.
    ![](https://i.imgur.com/UVPUpFu.png)
    
    基本原則:
    每一題皆先求$\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:
    ![](https://i.imgur.com/DY8zrl0.jpg)
    
    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))$.
    
    ![](https://i.imgur.com/VIEszGk.png)
    
    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$
    
    ![](https://i.imgur.com/JU7JMhn.png)

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:
        ![](https://i.imgur.com/FyM6J7k.png)

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$
        ![](https://i.imgur.com/xgln6HH.png)
    
    b. $T(n)=T(9n/10)+n$
        ![](https://i.imgur.com/1qzofur.png)

    


        



