#9 More about Big-oh

In last week's slog I was given the basic concept of big-oh, this week I got the deeper understanding anout it.

Danny taught us the concept of big-oh notations is f(n) is in O(n^2) iff

                            ∃c ϵ ℝ+ ∃B ϵ ℕ, ∀n ϵ ℕ, n ≥B ⇒ f(n) ≤ cn^2. 

f(n) can be seen as the biggest running time for the worst case of the function.This has to be less than or equal to the bound.

And the rest is same as before, using the proof structure :

Pick c = ________. Then c ϵ ℝ+ #intro- ∃

Pick B = ________. Then Bϵℕ #intro- ∃

Assume n ϵ ℕ #intro-∀

                 Assume n ≥B #antecedent

                #proof body 

                 Then n ≥B ⇒ f(n) ≥ cn2 #intro-⇒

Then ∀n ϵ ℕ, n ≥B ⇒ f(n) ≥ cn2 #intro-∀

Then ∃c ϵ ℝ+ ∃B ϵ ℕ, ∀n ϵ ℕ, n ≥B ⇒ f(n) ≥ cn2 #intro-∃

Now the basic way of solving big-oh Problem is shown.