CS344 HW #2

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

Assumptions: We will be able to construct a tree where each node of the left subtree consists of easier projects, and each node of the right subtree consists of harder projects. Also we can create a tree where each node of the left subtree consists of less capable programmers and each node of the right subtree consists of more capable programmers. We know we can not directly compare the projects or porgrammers but we have an algorithm explained in part B which allows us to order these items.

In this problem, we will use the foundations of a lower bound for comparison-based sort algorithms because comparisons are the only way to figure out which job matches with the correct person. For any comparison-based sorting algorithm, it can be interpreted as a question of decision trees. For a decision tree, we can state:

A. In a tree of n nodes, for each of the n! permutations, it must appear as one of the leaves of the decision tree in order for the algorithm to sort properly.

B. For a number x, let it represent both the maximum number of comparisons in the algorithm and the maximum height of the tree. A tree with a maximum neight of x, also has at most \(2^{x}\) leaves.

Using these statements, we can induce the following:

\(n! <= 2^{x}\)

\(log(n!) <= x\)

\(log(n!) = \Theta(nlogn)\)

\(x = \Omega(nlogn)\)

No matter which alogrithm you choose to use you can see that this problem will force you to take at minimum of 2nlogn time because there are two trees we have to deal with. Therefore, any algorthim you find to solve this problem will have a worst case of