(CSC165)_Nov15_BigOh/Omega/Theta(Week 9-10 Topic)

For these TWO weeks, we learned three major topics in evaluating the efficiency of programs, and they are Big-Oh, Big-Omega, and Big-Theta.

Based on what we can do in counting steps, we may be able to establish a specific formula for the program, and very possibly we may just get an general idea about the program. For example, it is Cn^3+K, CK^n, or Clnn (where, n is variable, C and K are constants). In these general form, the three topics helped us the categorize these programs. More specifically, Big-Oh gives us an upper bound, Big-Omega, gives us a lower bound, and Big-Theta is a tight bound, which is like a upper and lower bound.

So, more precisely, for any function f, which takes input of natural number and gives output as positive real number, we define Big-Oh, Big-Omega and Big-Theta respectively as following:

So, the questions we will possibly encounter in these topics may include prove or disprove of a given function in Big-O, Big-Omega, or Big-Theta. The basic steps of proving it:

1) pick c, and b

2) assume a generic n 

3) assume antecedent

4) connect antecedent with conclusion

5) close the assumptions

Actually making the connection between antecedent and conclusion is the most hard part of the proof. However, in general, after determining the goal, we can work on two different directions (reducing the larger element to approaching the smaller one and the other way around). In fact after going through the examples in lecture and questions in tutorial, I find there is always a relatively big space for us to approach the conclusion. Thus, there normally won't be a single right answer for these questions.

On the other hand, we disprove the statement by following the proof structure and prove the negation of the statement. I personally feel disproving is harder than proving, since it is harder to "pick" that n in accordance with assumed generic B or c. So, I should definitely work more on these kind of exercise.