# Big-O notation

1. Jun 20, 2008

### Cyborg31

1. The problem statement, all variables and given/known data

1. Prove the following subset relationships:
a. $$Constant \subseteq Logarithmic$$
b. $$Logarithmic \subseteq Linear$$
c. $$n log n \subseteq Polynomial$$
2. Relevant equations

O(1) Constant
O(log n) Logarithmic
O(n) Linear
O(n log n) n log n
O(n^m), m > 1 Polynomial of order m

3. The attempt at a solution
a. There exists an c, k element of Z where f(n) =< C * 1, f(n) =< C log n for all n => k.

So to show that Constant is a subset of Log, I need to show 1 =< C log n, And I find a C and k that satisfies that condition right? C = 1 k = 2

b. C = 1 k = 1 then log n =< Cn = log 1 =< 1 * 1

c. C = 1 k = 1 then n log n =< n^2 = 1 log 1 =< 1^2

Last edited: Jun 20, 2008
2. Jun 23, 2008

### mistermath

I'm not sure I can help but here goes.. for a, you want to show that after a while,
f(x) = c <= log n.

Well easiest way is imo to do lim n->\infty C/Log N = 0. Not sure if that is a proof, so you might consider:

Log n = C -> 10^c = n -> for n >= 10^c, log n > c. // as log is an increasing function

for b, you can look at lim n->\infty Log N / N = 0. (or opposite = infitity) but proof wise consider you want to prove log n <= n for all n > some number.

If you look at the graph, this is true for all of them, maybe use induction?