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......

Week 6: Cases, multiple quantifiers, limits

Proof about non-boolean functions
Boolean function - a function whose return value is True/False - example x>5
Non-boolean function - not a function of such as above - example x^2
Floor for x - the largest integer that <= x
Steps to proof one is correct
1) fully understand the definition
2) breaks the definition into predicates
3) play around with those predicates
4) proof!

Proof something false
To disprove a statement S, just proove NOT S
1) negate the statement properly
2) prove the negation

Proof by puns (SERIOUS PROOF)
A cow have four more legs than no cow.
No cow has five legs.
Therefore, a cow has nine legs.

Proof by intimidation (ALSO VERY SERIOUS TECHNIQUE)
Trivial!!!!!
or
Don't be STUPID, of course it's true!

Proof by intuition (WHO DOESN'T)
I have a dre... I mean I believe....!

Proof by clever variable choice (BE SMART ABOUT IT)
Let A be the number such that this proof works...

Proof by hasty generalization (WELL IF IT WORKS IT WORKS)
Well, it works for 17, soooo~

Proof by tautology/begging the question (FOR ALL THE BELIEVERS)
God exist because the BIBLE said so!

Proof by convenience
It would be nice if it were true, so.....

Proof by beautiful typesetting (...Yea)
Because the proof looks good and is typed in LaTex...

Proof by *%^*% (Can't read)
I^$#%&*^$&^#

Proof about limits
OK I am done with limits, so they are like out of my limit...
but I will say this
Wise choices are often found by backward search
DON"T freak out unnecessarily!

Week 5 Term Test ~ Contradiction, existence, sequences

Proof using contrapositive

the proof for P IMPLIES Q also proves NOT Q IMPLIES NOT P, and vice versa

Hence we can prove P IMPLIES Q by proving its contrapositive 

Use when the reverse direction is easier to prove than the original

Proof using contradiction

Assume predicate logic P, then by P and some axioms we come to a contradiction, hence NOT P

Proof for existence

Find a single example, show the predicate logic applies

Proof about a sequence

It is not much different as proving a regular expression, the key is to take the sequence definition as predicates, often works better if you write out the first 10 terms of the sequence to visualize it.