Week 10

For this SLOG entry, I will be doing a detailed solution to a question on a previous exam:

Understand the problem:
    This question is asking for a proof that the function f(n) = n is in big Theta of g(n) = n^2. I know that for a function f to be in big-Theta of another function g means that f is both upper and lower bounded by g. By intuition, I know that a linear function cannot be lower bounded by a quadratic function, as the quadratic function will eventually become larger than the linear function. So, I just need to prove that f(n) is not in big Omega of g(n).

Devise a plan:

 First, I need the definition of big Theta.

However, it is a more useful definition to just say that f is in big O and big Omega of g. To negate this simpler statement, I would say that f is not in big O of g, or f is not in big Omega of g. I only need to prove one of these, which is that f is not in big Omega of g.

So I need to prove the negation of this, which is: ∀ c∈ℝ⁺, ∀ B∈ℕ, ∃ n∈ℕ, n ≥ B ∧ n < c(n²)

Carry out the plan:

Finding an n:

n' ≤ n'^2

n' ≤ n' * n'^2 

n' < c * n'^2  #as long as n' > 1/c, so pick n' = max{ceiling(2/c), B}

2/c < c(2/c)^2
      = c(4/c^2)
      = 4/c
2/c < 4/c
2 < 4

Assume c∈ℝ⁺ and B∈ℕ  

    

    Pick n' = max{ceiling(2/c), B}

    ceiling(2/c) ∈ℕ, B∈ℕ, so n'∈ℕ

    max{ceiling(2/c), B} ≥ B, so n' ≥ B

    n' ≤ n'^2 
    n' ≤ n' * n'^2

    n' < c * n'^2   # Since n' > 1/c

Then ∀ c∈ℝ⁺, ∀ B∈ℕ, ∃ n∈ℕ, n ≥ B ∧ n < c(n²)
Then f∉ Ω(g)
Then f is not in big Theta of g.