Week 8: big-Oh and big-Omega + worst cases analyses + problem solving

From 8th week I've started to find proofs are more and more interesting through lectures and the assignment.  Each step is there preparing for the next step. The lectures of 2 weeks were focused on proofs about big-Oh and big-Omega and a little algorithm(insertion sort and maximum slices).


Tips for piking c and B while proving big-Oh:
1. c should be larger than the coefficient of the highest n term
2. assume n = 1, then pick c = the value of the function
3. doing "forward"and "backward" strategies learned from tutorials to find appropriate c



Steps for proving some non-polynomial function f(n)not in big-Oh(g(n)):
1. prove f(n)/g(n) diverges (use limit)
2. translate the limit into its definition
3. pick a wise n which bigger than n' and B
4. start writing the structure of the proof



Tips for maximum slice based on the example taught in lecture:
1. for worst case, Wms(n) is in O(n^3):
   for every loop:
   largest number of steps = n*(the number of steps contains in the loop) + 1

2. for lower-bound case, Wms(n) is in big-Omega(n^3):
   smallest number of steps = (n/3)^(the number of loops)

Encountered Problem: design a max_sum runs on O(n)...I still can not work that one out, the function I wrote on Python always returned a number slightly different from the number should be returned.



Summary for insertion sorting:

Step 1.derive the exact format of Wis(n)
for worst case
  n-1= number fo iterations  "3"is the number of steps in the inner loop
 "5"is the number of other steps in the function other than the inner loop

each iteration has （3i + 1）+ 5 to execute

Step 2. then determine it's whether upper-bounds or lower-bounds

As more variables come up, we are more confused, like Timothy's title of week8: "Confusion Grows As Complexity Grows". By following his slog, I found another slog worth of reading and following: http://yahuiliuslog165.blogspot.ca/
Every week she analyzes one or two questions in her slog. Unlike Timothy, she likes writing more about problem-solving, which is rather helpful once I kind of grasp the concepts. :)