We started off this lecture with a big-omega proof. It is similar to a big-oh proof, only in that we underestimate the function and over-estimate the inside of the bracket.
Takeaway:
-magic breakpoint B=1
-simplify the function without changing the highest degree
Next, we learned the proof of general statements for big-Oh: using a definition of function sets, we can group functions together. For example, all the functions we work with take in a natural number, and return a non-negative real number. For these problems, the main point is to find a relationship between the c values, B values and that of the others. A relationship (comparative) can be manipulated to prove a statement or definition.
Computability:
The next part of our lecture was on Computability. Computers cannot solve everything, as there are some functions that are impossible to define. These will cause infinite loops or/and causing the program to crash.
However, if we can reduce a function to another one, then we just need to find the computability of the reduced function.
computable implies computable, and non-computable implies non-computable.
Tuesday, November 25, 2014
Wednesday, November 5, 2014
Week 9: Big- Oh Proofs
In this week of lecture we learned how to prove using the definition of Big-Oh.
Using the definition, the basic concept to grasp is finding a c and B, that past the threshold B, the definition holds. Even with a constant, we let n=1 and calculate the value. For example, to prove 3n^2+2n+5 is in O(n^2), we let n=1, so the function calculates to 10. We let c=10, and B=1. For all n>1, 10n^2 will be greater than the function, so it holds.
For more complex O and functions, we meet the two in the centre. We overestimate the function, and underestimate the O. For example, for function 7n^6-5n^4+2n^3 <= 7n^6+2n^3 <= 7n^6+2n^6 = 9n^6. Vice versa for underestimating.
In order to disprove, we just prove the negation. This also involves picking a smart B and c value.
For non-polynomials, we prove using limits. To find a function not in a bigoh: We find a breakpoint n' so that for n>n', function/bigohfunction > c. That is, that beyond a threshold, the function is always bigger than the bigohfunction.
Using the definition, the basic concept to grasp is finding a c and B, that past the threshold B, the definition holds. Even with a constant, we let n=1 and calculate the value. For example, to prove 3n^2+2n+5 is in O(n^2), we let n=1, so the function calculates to 10. We let c=10, and B=1. For all n>1, 10n^2 will be greater than the function, so it holds.
For more complex O and functions, we meet the two in the centre. We overestimate the function, and underestimate the O. For example, for function 7n^6-5n^4+2n^3 <= 7n^6+2n^3 <= 7n^6+2n^6 = 9n^6. Vice versa for underestimating.
In order to disprove, we just prove the negation. This also involves picking a smart B and c value.
For non-polynomials, we prove using limits. To find a function not in a bigoh: We find a breakpoint n' so that for n>n', function/bigohfunction > c. That is, that beyond a threshold, the function is always bigger than the bigohfunction.
Subscribe to:
Posts (Atom)