Big-O notation

  • Thread starter Cyborg31
  • Start date
  • #1
38
0

Homework Statement



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

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
 
Last edited:

Answers and Replies

  • #2
52
0
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?
 

Related Threads on Big-O notation

  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
3
Views
11K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
18
Views
35K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
3
Views
15K
Replies
8
Views
10K
  • Last Post
Replies
5
Views
2K
Top