- #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: