Week 7: Sorting algorithm complexity, big-Oh

Now moving past the basics of proofs, we are getting into an interesting field of CS finally!
Sorting Algorithm Complexity! RUN FOREST RUN! oh, I mean Run Time Calculation.

BUT FIRST, let me take a selfie!
I mean go through what we had no time last lecture

Proof by cases
1) Split your argument into differences cases (make sure all cases together in disjunction is a tautology)
2) Prove the conclusion for each case

The famous example:
If you have a problem in your life
Case 1: You can do something about it
~ don't worry
Case 2: You can't do anything about it
~ don't worry
You can do something OR you can't do anything is a tautology
Conclusion ~ don't worry

Uniqueness
If m and n are natural numbers, with n NOT 0
then there is exactly one pair natural numbers (q,r) such that
        m = qn + r
divide m by n, the quotient and remainder are unique

NOW Algorithm analysis!
Worst Run Time - the maximum number of steps the algorithm will execute on input size n - O(something n)
1) But we don't really care about the number of steps, what we actually care about is how the number of steps grows as the size of input grows - that means, we don't care about the absolute number of steps, hence 0.5n^2 and 700n^2 are NO different. Constant factor does not matter!
2) we care about large input sizes, that is when n is very large, so n^2 and n^2+n+2 are NO different. Only the highest order term matters

O(f(n) is the asymptotic upper-bound
~The set of functions that grows no faster than f(n)

Best Run time - the minimum number of steps the algorithm will execute on input size n - Omega(n)
similar idea!

QUICK NOTE
In CSC165, sometimes we use asymptotic notations such as O(n²), and sometimes, when we want to be more accurate, we use the exact forms, such as 3n² + 2n. Depends on the question asked.

To find the exact forms, we need to examine the function......