Subset Relationships: Constant, Logarithmic, and Polynomial in Big-O Notation

[Cyborg31]

Homework Statement

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

Homework 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

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

 

[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?