# 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)}$$

\