Consider the twelve functions of n (recall that lg denotes the binary logarithm):

n n5 n lg(n) n!

p

n 3

p

n

lg(n) lg(n!) ln(n) 2n (1:01)n 700; 000

1. Arrange these functions in non-decreasing order of growth; that is, nd an arrangement

f1 f2 : : : f12 of the functions such that f1 2 O(f2), f2 2 O(f3), . . . f11 2 O(f12).

For each i, you should write fi = fi+1 if fi 2 (fi+1), and write fi (unlike the pathological example in Question 2, one of the two will always hold). You

do not need to argue for your answers.

2. For each function X, roughly approximate how big n must be in order for X(n) to be

at least 100,000, and to be at least 10,000,000,000 (1010).

 

Considerthetwelvefunctionsofn(recallthatlgdenotesthebinarylogarithm):nn5nlg(n)n!√n3√nlg(n)lg(n!)ln(n)2n(1.01)n700,0001. Arrange these functions in non-decreasing order of growth; that is, Fnd an arrangementf1≤f2≤...≤f12of the functions such thatf1∈O(f2),f2∈O(f3), ...f11∈O(f12).±or eachi, you should writefi=fi+1iffi∈Θ(fi+1), and writefi< fi+1iffi∈o(fi+1)(unlike the pathological example in Question 2, one of the two will always hold). Youdo not need to argue for your answers.2. ±or each functionX, roughly approximate how bignmust be in order forX(n) to beat least 100,000, and to be at least 10,000,000,000 (1010).

Attachments:

• 1495178270-3.pdf