Prove:

1. n log(n) is not (n)

2. sqrt(n) = o(n), where sqrt(n) is the square root of n

3. if T(n) = o( f(n) ) then T(n) = O( f(n) )

4. for any b > 1, n! = omega( bn )

Given:

1: T(n) is 1( f(n) ) if both T(n) = O( f(n) ) and T(n) = ( f(n) )

2: 2: () = 2( f(n) ) if 1, 2, no > 0 such that n no

0 c1 f(n) () <= c2 f(n)

Prove:

5. if T(n) is 1( f(n) ), then T(n) is 2( f(n) ) must also be true