0% found this document useful (0 votes)
23 views1 page

Lecture04 1

Download as pdf or txt
Download as pdf or txt
Download as pdf or txt
You are on page 1/ 1

Solution to Exercise 1, Lecture 4

Sept 27, 2001


Exer 1, Lecture 4: Show that Proof: We must show that (1) n i=1 log i. For (1)
n i=1 n i=1

log i n log n. log i n log n and (2) that n log n

n i=1

For (2), we use a geometric picture that utilizes rectangles of height log i (starting at i = 2 since log 1 = 0) and width one along with the graph of the function log x to see that
n n

log i

n i=1

log n = n log n.

log i >
i=1 1

log xdx = (x log x x)|n = n log n n + 1 > n log n n. 1

Now we need to show that nlogn n n log n. That is, we need to nd a constant c > 0 and an integer n0 > 0 such that c(n log n n) > n log n for n > n0 . However, c(n log n n) > n log n if and only if (c 1)n log n > cn if and only if (c 1) log n > c c if and only if log n > c1 . Let c = 2, then log n > c/(c 1) when n > 4. Summarizing, thus with c = 2 and n0 = 4, we have that
n n

n log n < 2(n log n n) < 2(n log n n + 1) = 2

log xdx < 2


1 i=1

log i

when n > n0 . Thus, by the denition of dominance, we have that n log n n i=1 log i. B. F. Caviness Univ. of Delaware

You might also like