CSC165H1F - 8th week

In the first lecture of the week, we talked about time complexity and running times of programs. As an example Danny gave us some programs including a while loop in it. We calculated the steps of each line in program in terms of length. It was really a fun work. We also found how many steps will happen if the first index where x is found is j. I think I understood most of the work we did in the first lecture of the week. Then in the second lecture we started talking about the upper and lower bound of the worst case. The worst case is at least as bad as the lower bound and the worst case is no worse than the lower bound. It wasn't that hard to understand the definition of the lower and upper bound and write it in terms of logic. Then we proved the logical definition of the lower and the upper bound.  It took us time to prove these two and I had really hard time understanding the proofs because they are so long and they require so much thinking.

As Junru Shao wrote on his Slog: "When Proving Big Omega, proof structure looks like this.

Let c = __
Let B = __
Assume n ∈ N
     Assume n >= B
        
                  .
                  .    #playing around number until I get f(n)>=c g(n)

          Then f(n)>=c g(n)
     Then n>= B  ->f(n)>=c g(n)
Then  ∃ c ∈ R+    ∃ B ∈ N     ∀n ∈ N    n>=B  ->  f(n)>=c g(n)"

I think its a long proof and its hard to memorize it.