CS344 HW #2

Question 1

  1. \(T(n) = 2T(\frac{n}{4})+n^{0.51}\)

    Using Master’s Theorem \(T(n)=aT(\frac{n}{b})+f(n)\), we let \(a=2\), \(b=4\), and \(d=.51\).

    \(T(n) = \theta(n^{0.51})\)

  2. \(T(n) = 16T(\frac{n}{4}) + n!\)

    We can use Case 3 that was given (\(f(n) = \Omega(n^{log_{b}a+\epsilon})\) ) to analyze the recurrence relation.

    \(f(n)= n!\) and \(n^{log_{b}a+\epsilon}\) for \(\epsilon > 0\)

    Case 3 states that if \(f(n)=\Omega(n^{log_{b}a+\epsilon})\), then \(T(n) = \theta(f(n))\)

    Since \(n!=\Omega(n^{2}+\epsilon)\), then:

    \(T(n)=\theta(n!)\)

  3. \(T(n)= \sqrt{2}T(\frac{n}{2})+logn\)

    For this problem, we can first use Case 1 to analyze the recurrence relation.

    \(f(n)=log(n)\) and \(n^{log_{b}a-\epsilon}=n^{\frac{1}{2}-\epsilon}\)

    We know from Case 3, that if \(f(n)=O(log_{b}a-\epsilon), then T(n) = \theta(n^{log_{b}a})\).

    Since we know that a polynomial is greater than a log function, we can apply case 1, therefore:

    \(T(n) = \theta(\sqrt{n})\)

  4. \(T(n) = T(n-1) + lg(n)\)

    \(T(n-1) = T(n-2) + lg(n-1)\)

    \(T(n-2) = T(n-3) + lg(n-2)\)

    \(T(1) = T(0) + lg(1)\)

    \(T(n) + \sum_{i=1}^{n-1} T(i) = \sum_{i=1}^{n-1} T(i)\) since \(T(0) = T(1) + \sum_{k=1}^{n} lg(k)\)

    Then, subtract the summation terms from both sides and:

    \(T(n) = \sum_{k=1}^{n} lg(k) = lg(n!) <= \theta(nlgn)\)

  5. \(T(n) = 5T(\frac{n}{5})+ \frac{n}{lgn}\) So if we are to look at the recursion tree this relation creates we can observe that at the jth level there will be \(5^j\) nodes. Each node will only have a problem of the size \(\frac{n}{5^j}\) so at each node the time to complete it will be \(\frac{(\frac{n}{5^j})}{log(\frac{n}{5^j})}\)

    Know this if we sum over all the \(log(n)\) levels we get:

    \(T(n) = \sum_{j=0}^{log(n-1)} 5^{j}\frac{\frac{n}{5^j}}{log(\frac{n}{5^j})}\)

    \(T(n) = \sum_{j=0}^{log(n-1)} \frac{n}{log(n-j)}\)

    \(T(n) = n\sum_{j=1}^{log(n-1)} \frac{1}{j}= \theta(nlog(log(n)))\)