Big O, Big Omega, Theta - Slog #8

When we first learned about Big O, Big Omega and Theta this past few weeks, I often went into a blank state as to what the definitions were.
To sum it up,
Big O: O(g) = {f : N -> R+, ∃ c ∈ R+, ∃ B ∈ N, ∀n ∈ N, n ≥ B => f(n) ≤ c g(n)
Function f is bounded above by function g (constant factor of c).

Big Omega: Ω(g) = {f : N -> R+, ∃ c ∈ R+, ∃ B ∈ N, ∀n ∈ N, n ≥ B => f(n) ≥ c g(n)
Function f is bounded below by function g (constant factor of c).


Theta : Θ(g) = {f : N -> R+, ∃ c ∈ R+, ∃ B ∈ N,  ∀n ∈ N, n ≥ B => c1 g(n) ≤ f(n) ≤ c2 g(n) 
Note: It's basically the combination of Big O and Big Omega. 

Function f is bounded above by function g by a constant factor of c2 and bounded below by the same function with a constant factor of c1.

Reminiscing Pre/Post Test - Slog #7

In honest truth, I had initially feared that we'll be tested on proving/disproving limits (epsilon and delta proofs) since there were very few examples provided.

An example from the lecture:
∀ϵ ∈ R+, ∃ δ ∈ R+, ∀ y ∈ R, | y - π | -> |y^2 - π^2| < ϵ

To my understanding, (I hope) this means:
"For all epsilon, there exist a delta so that for all y is δ units of π implying that  
lim       y^2 = π^2
x -> π
As to providing the "body" of the proof, it's still a very vague topic and I hope through further practice and possibly future visits to office hours, this could be clear up. 

To my relief, I found the term test to be relatively fair since it incorporated proofs similar to the ones from the lecture and tutorials. When the solutions came out, I was stunned that the third question concerning "floor" was much easier than what I wrote down.

In essence,  I become worrisome before testing, and even more worried post-test while waiting for the marks.

Upcoming Test & Assignment 2 - Slog #6

Now that we have wrapped up the introduction to proofs, I can confidently admit that proofs are fun to tackle. Surely, it takes sometime to understand and decide whether to prove or disprove the statement. Even when that's all figured out, the challenge was actually writing up the "body" of the proof. In my group, we extensively attempted direct proof, indirect proof and contrapositive to conjure up a sensible solution. Oppose to watching the professor write the proofs and unanimously agreeing, this assignment was great practice in independently building up my proofs. Although I found the majority of the questions to be fair, my group oddly stumbled on question 1. The difficulty arises from transitioning a single inequality (such as a < b)
to a transitive inequality (a < b < c).

As for the next term test, I'm quite worry since I tend to linger on a question longer than time provided. Especially with the topic of complexity. Tutorial was useful in helping us determine the number of steps of a program.For instance, we were told that for every +,-, =, >, <, [], while, and, len operations, a extra 1 step is carried out. Using summation to determine the general equation of steps takes sometime but it's not too difficult. What I'm more worried about is writing the asymptotic proofs.