Week 8

• We took a look into Big Oh this week. We identified the expression of Big Oh as finding a constant c, past a breakpoint B, where the graph of f(n) (can be any expression) is always less than c ( a constant) multiplied by g(n) ( can be any expression). Here is an example of a big Oh proof stated below:

Let c = ....... and B = ............

Then c ∈ R⁺and B ∈ N.

Assume n ∈ N. # in order to introduce ∀

       Assume n ≥ B'. # antecedent; B is an arbitrary natural number

            .

            .

            .

Then ∀ n ∈ N, n ≥ B ⇒ g(n) ≤ cf(n) # introduce ∀ and ⇒

Then ∃ c ∈ R⁺, ∃ B ∈ N, ∀ n ∈ N, n ≥ B ⇒ f(n) ≤ cg(n) # introduce ∃ for b and c

 

• Understanding the proof structure and the definition of Big-O is based on understanding the graph . Proving it requires more practice because it all depends on which statements we get. For instance, Big-O can be done with two functions and polynomials. The proof structures are similar. But to enhance our proof, it's crucial that we begin with scratch work before going on to write the proof.
  

  
•  Also we learnt about analysing algorithms, looking at worst and best case scenarios. Merge sort was in O(nlogn) where bubble sort was in O(n^2) . Looking forward to some more algorithms. Anyways test 2 is next week and I am not too sure about it but we'll see.