Week 10 (Problem Solving)

Not much happened this week, so I decided to do a problem solving episode on a problem in the tutorial exercise.
Prove 5n^4 - 3n^2 + 1  is in O(6n^5 - 4n^2 + 2n )

First by looking at this question, you know it's probably true because 6n^5 has a higher degree than 5n^4, so it will eventually outgrow the other function.

 The idea is to make the first function larger and second function smaller to prove that F1 <= C (F2) and prove it by transitivity since F2 is smaller than 6n^5 - 4n^2 + 2n and the F1 is larger than  5n^4 - 3n^2 + 1, so 5n^4 - 3n^2 + 1 <= C(6n^5 - 4n^2 + 2n)

So to make 5n^4 - 3n^2 + 1 larger we can remove the -3n^2, and make +1 to be +1(n^4), which is true for all n >= 1. So the F1 we are looking for is (5+1) n^4 = 6n^4

To make  6n^5 - 4n^2 + 2n smaller we can remove the +2n, and make -4n^2 to be -4n^5, which is true for all n >= 0. So the F2 we are looking for is (6-4) n^5 = 2n^5

To make them easier to compare we can make F1 to be 6n^5 since 6n^5 > 6n^4 for all n>=0. So
6n^5 <= C 2n^5 by choosing C to be 3

So this is the rough work for that question, and then we can write the detailed proof.