Week 8

In the lectures of this week, we expanded bit more on the analysis and proof of worst cases. Also, the second term test would happen next week on Wednesday on proofs of various claims. I would be preparing for it by redoing some examples that we did in lectures and also the past test from last year.

Next, on previous week, we mentioned briefly about why we as computer scientists cared about worst speed. This week, we expanded a bit more on proving worst cases.

First of all, we started with linear search.

 

In the example above, we tried to find the running time of this code by counting steps. We wanted to idealize time of counting the number of steps for a given input. 

Worst Case - Upper Bound and Lower Bound:

 

Upper Bound and Lower bound of a program:

1. tp(x) stood for the time that required to count the steps of the program.

2. C stood for a constant value.

3. B stood for a break point (what we used to determine whether the tp(x) was upper bounded or not. 

U(n) = n^2 because 

U = n, so n(n) = n^2

Therefore,  we could conclude that tp(x) was upper bounded by cn^2 and tp(x) was also lower bounded by cn^2. 

In conclusion, we now knew that:

Big Oh(n^2) meant the set of functions that would grow no faster than n^2

Big Omega(n^2) meant the set of functions that would grow no slower than n^2 

When set of functions that were in both upper bound and lower bound, then we ended up having Big Theta(n^2), which it meant the set of functions grew as fast as n^2