Lecture04 1
Lecture04 1
Lecture04 1
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
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
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