Big oh

1. Jun 18, 2008

aaa59

O(1) is constant
O(log n to the base 2) is logarithmic
O(n) linear

how would you prove that constant is a subset of logartihmic?

2. Jun 18, 2008

Werg22

O(1) = O(log_2 1) = O(0)

3. Jun 19, 2008

aaa59

I should have been clearer.

given "Big-Oh" sets
O(1): constant
O(log2(n)): logarithmic
O(n): linear
O(nlog2(n)): n log n
O(n^3): cubic
O(n^m), m>1: polynomial of order m
O(c^n), c>1: exponential
O(n!): factorial

Prove
Constant is a subset of logarithmic
logarithmic is a subset of linear
n log n is a subset of polynomial
exponential is a subset of factorial

Thank you

4. Jun 19, 2008

gunch

Most follow fairly easily from the definition of Big-Oh. For instance let f be an arbitrary function in O(1). We now wish to show that f is in $$O(\log_n(n))$$. Because of the definition of O(1) there exist some $$x_0$$ and M such that $$f(x) \leq M$$ for all $$x > x_0$$. Now let $$x_1 = \max(x_0,n)$$ then $$f(x) \leq M \leq M\log_n(x)$$ for all $$x > x_1$$ so $$f(x) = O(\log_n(n))$$. Here we took advantage of the fact that the logarithm is increasing and $$\log_n(x) \geq 1$$ when $$x \geq n$$.

If you have problems with any specific steps you should post the specific problem you're having.