Thursday 21 March 2013

Clarifying Big-Oh

Big-Oh notation was a weird concept to me at first, especially when Professor Heap told us that we could just choose to drop values from within the given functions. But after going through the steps it started to make a lot more sense.

Since we are saying that the function that we are making bigger is bounded above by a function that we are making smaller, even if we only have to multiply by a small constant factor. If it is true for that then it is true for all natural number.

Here's a run through from one of the tutorial examples:

Statement: ∃c ∈ R, ∃B ∈ ℕ, n ℕ, n ≥ B ⇒ 5n4 - 3n2 + 1   c(6n5 – 4n3 + 2n)

      Pick c = 3, Then c ∈ R
       Pick B = 1, Then B ∈
      Assume n ℕ                        # n is a generic natural number, to introduce ∀
                  Assume n ≥ B                        # assume antecedent, to introduce ⇒
                              Then 5n4 - 3n2 + 1
  • Since we're saying that  5n4 - 3n2 + 1 is bound above by c(6n5 – 4n3 + 2n) we can continue to make it larger and if it is still bound above then we know it is true.

                              5n4 + 1        # Remove (-3n)

  • For all the natural numbers past the break point, we can safely prove that this will be bound above by this. 

                              5n4 + n        # n 1 hence B = 1
                                             = 5n4  + n4
                                             = 6n5                      # Multiply by n
  • Here we pick the c, so that this function is true for all natural numbers N. c this helps scale the function to make this true for all natural numbers.

                                             = 3(2n5)                     # c = 3
                              = c(6n5 – 4n5)
                              c(6n5 – 4n3)
                              c(6n5 – 4n3 + 2n)
  • Since  c(6n5 – 4n3 + 2n) is what we are bounding by we can continue to make it smaller for the same reason stated above, because if this still bounds the bottom function above then it is true for the much larger function.

                              Then 5n4 - 3n2 + 1  c(6n5 – 4n3 + 2n)
                  Then n ≥ B ⇒ 5n4 - 3n2 + 1  c(6n5 – 4n3 + 2n)  # conclude
      Then n ℕ, n ≥ B ⇒ 5n4 - 3n2 + 1  c(6n5 – 4n3 + 2n)            # conclude
            Then ∃c ∈ R, ∃B ∈ ℕ, n ℕ, n ≥ B ⇒ 5n4 - 3n2 + 1  c(6n5 – 4n3 + 2n)                                                                                                                   # conclude

No comments:

Post a Comment