\(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})\)
\(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!)\)
\(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})\)
\(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)\)
\(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)))\)