Examples for ICS 311 Topic 03

4n³ is Θ(n³):

To approach this, we start by writing out the definition of Θ with f(n) = 4n³ and g(n) = n³: Show that ∃ c₁, c₂, n₀≥ 0 such that for all n ≥ n₀,

c₁n³   ≤   4n³   ≤   c₂n³.

Try c₁ = c₂ = 4; n₀ = 1:

4n³   ≤   4n³   ≤   4n³.

That was too easy! It's harder when you need to absorb a lower order term:

4n³ + 2n is Θ(n³):

Show that ∃ c₁, c₂, n₀≥ 0 such that ∀ n ≥ n₀,

c₁n³   ≤   4n³ + 2n   ≤   c₂n³

Try c₁ = 4; c₂ = 5. (I chose c₁ = 4 to make the first term more like the second: certainly adding 2n will make it larger. I chose 5 since the right hand term has to grow larger.)

4n³   ≤   4n³ + 2n   ≤   5n³

Divide by n³:

4   ≤   4 + 2/n²   ≤   5

This is true for all n ≥ n₀ = 2, since the term 2/n² will always be larger than 0 (satisfying the first inequality) but less than 1 (satisfying the second inequality).

You should be able to do similar analyses.