Solving a problem on assignment 3

I will now attempt to write out my thought process in solving problem 3 of assignment 3.

1. UNDERSTANDING THE PROBLEM 
Prove or disprove: 15n2 is in Ω (3x 2ⁿ).
I know that f(n) in Ω(g(n)) means that after a certain n, f(n) is always larger than g(n).
First I need to figure out if this statement is true or not, so for help, I decided to graph the two lines.

It was obvious that while 15x² started off outputting bigger, 3* 2^x eclipsed it later on. Which means that that the statement is wrong.
2. DEVISING A PLAN
I knew that in order to prove that the statement was wrong, I needed to prove the contrapositive of the statement, which is: ∀c ∊ ℝ, ∀B∊ ℕ, ∃n∊ ℕ, n  ≥ B ⋀ g(n)  < c f(n).
With a little help from the hint from the question, I figured out that I need to use limits and l’Hopital’s rule to prove using the definition of a limit that g(n) < c f(n).

3. CARRYING OUT THE PLAN
I start out my proof as usual, assuming the ∀s.

Assume c ∊ ℝ⁺ and B ∊ ℕ.   

I want to show that the limit as n → ∞ (15n²/3 x 2ⁿ) is zero which would prove that the denominator, 3 x 2ⁿ is exponentially larger than the numerator (15n²), thus making the claim that 15n² is bigger than 3 x 2ⁿ false after a certain n.

Let L = lim_{n →∞} 15n² / 3 x 2ⁿ

Then L = lim_{n →∞} 30n / 3ⁿ x 2^n-1         # L’Hopital’s Rule

Then L = lim_{n →∞} 30 / 3n² - 3ⁿ x 2^n-2     # L’Hopital’s Rule Again

Then L = 0     # 1/∞ = 0

Now I will write out the definition of a limit, and note that because c and ε are both ∊ ℝ⁺_, we can make c = ε.

Then ∃n0 ∊ ℕ, ∀n ∊ ℕ, n ≥ n0 ⇒ L - c < 15n2 / 3 x 2n < L + c    

Since L = 0,

Then ∃n₀ ∊ ℕ, ∀n ∊ ℕ, n ≥ n₀ ⇒ 15n2 < c (3 x 2n)

Let n₀ be such that ∀n ∊ ℕ, n ≥ n₀ ⇒ 15n2 < c (3 x 2n), and n’ = max (B, n₀)

Since B and n₀ are both ∊ ℕ:

Then n’ ∊ ℕ

Then n’ ≥ B        #By Definition of max

Then 15n’2 < c3 x 2n’     #By the lines above, since n’ ≥ n₀

Now let 2 functions g(n’) = 15n’², and f(n’) = 3 x 2^n’

Then n’ ≥ B ⋀ g(n’)  < c f(n’)    # ⋀ intro, g(n’) = 15n’², and f(n’) = 3 x 2^n’

Then ∃n∊ ℕ, n ≥ B ⋀ g(n)  < c f(n)    # ∃ intro

Conclude ∀c ∊ ℝ, ∀B∊ ℕ, ∃n∊ ℕ, n ≥ B ⋀ g(n)  < c f(n)     # ∀ intro

I have now proved the contrapositive, thus disproving the original statement.

4. LOOKING BACK

Let’s check the answer by observing the 2 functions at xs with high expected y, say x = 10:

15(10) ² = 1500.

3(2)¹⁰ = 3072.

And x = 11:

15(11) ² = 1815.

3(2)¹⁰ = 6144.

So it is obvious that 3(2)¹⁰ is NOT the lower bound for 15(10) ² because 3(2)¹⁰ is obviously growing at a much faster rate than 15(10) ².

Although there may be other solutions to solve this problem, I think this method, using limits is the easiest and cleanest method.

Halting Problem problems

Lately I feel as if I’m falling a little behind in this class. I’ve gotten a bit of a grasp on Big O and such, but the halting section still confuses me. I’ve spent a whole day looking at videos, reading class notes, and looking at the slides, but I don’t feel like they explained things fully. For example, in the slides, it says that “if a function is well defined…” What does “well defined” mean? I’ve tried looking it up, and the explanations seem more complicated than anything I’ve seen before. Also, the part about how one function reduces to another still confuses me. On the third assignment, there is a hint to question six where it says to reduce the halt function to prove that the function is non-computational. In the notes, there was a slide explaining how one, “f” function reduces to another, “g”, but I was never sure which of the two functions halt falls into. Does the function reduce to halt, or does halt reduce to the function?

But the most confusing part of the whole section was that for non-computational functions, we know what x to put in to get the output, but we don’t know how it works? Of course we do! We have the code right there! If our human brain can look at the function and determine the input and corresponding outputs, doesn’t that mean that we just computed it in our head? Therefore, computable?

I guess I'll have to look at more material and watch some more videos to try to figure this out before our assignment is due.