Proof. See the textbook. Omitted.
Example 11
Obtain an asymptotic bound for the following recurrence relations using the master theorem.

T(n) = 9T(n/3) + n

T(n) =T(2n/3) +1

T(n) = 3T(n/4) + nlgn.
Solution:

T(n) = 9T(n/3) + n
lg_{b}a = lg_{3}9 = 2.
Set e = 0.5.
We have f(n) = n = O(n^{20.5})= O(n^{1.5}). Therefore,
T(n) = Q (n^{2}).

T(n) =T(2n/3) +1
lg_{b}a = lg_{3/2}1 = 0.
Since n^{0} = 1, the first rule in the Master Theorem is not applicable, but second rule can be applied. Therefore,
T(n) = Q (n^{0}lgn) = Q (lgn).

T(n) = 3T(n/4) + nlgn
lg_{b}a = lg_{4}3 = 0.793.
Obviously, the first two rules of the Master Theorem do not apply. We check the third rule. Setting e = 0.1, we have
f(n) = nlgn = (n) = ().
Moreover, we have
af(n/b) = 3(n/4)lg(n/4) ≤ (3/4)nlgn for any n > 1.
If we set c = 3/4, we will have, for any n > 1,
af(n/b) ≤ (3/4)nlgn = cf(n). Therefore, by the Master Theorem,
T(n) = Q(nlgn).

The Complexity of Problems
We notice that some problems are easier to solve, some are harder, and some are very difficult or even not solvable. For a given problem we wish to know how hard the problem is. When we have designed an algorithm, we also wish to know if we can do better, or if we have reached the bottom. For example, it is wellknown that any comparisonbased sorting algorithm needs at least lgn! comparisons to sort n numbers. Therefore, this result save researchers a lot of efforts and time to search for a better algorithm which will never be obtained. We define the Complexity of a problem to be the minimum time required to solve this problem.
Obtaining a complexity lower bound for a given problem is often an important topic. An algorithm is called optimal if its time complexity matches with the problem lower bound. But, before you can claim your algorithm is optimal you need to obtain its lower bound. We will discuss some techniques and results on this issue.
There are many difficult problems whose complexities are not known. For those problems, the best known algorithm needs an exponential time. A problem is called tractable if it can be solved in polynomial time, otherwise, intractable. Because the exponential function grows much faster than any polynomial function, we would like to draw a line between these two classes of functions. A problem that can be solved in polynomial time is said to belong to class P. There is a class of problems whose tractability is not known. What we know is that they can be solved by a nondeterministic computer in polynomial time. Problems that can be solved by a nondeterministic computer in polynomial time are said to belong to class NP. Class P is a subset of class NP. The NPcompleteness theory has been developed to characterize those NP problems for witch no polynomial time algorithm is known so far. Moreover, if any of them can be solved some day in polynomial time, then all NP problems can be solved in polynomial time. Those problems are said to belong to NPcomplete class. Obviously, if any NPcomplete problem is proven to be not polynomial solvable, then all problems in NPcomplete class are not polynomial solvable. We will discuss the NPcomplete problems and how to prove a problem to be in this class in Chapter 34.
End of Ch. 1.
Share with your friends: 