This week, we worked with proving the negation of big-Oh, omitted lots of bookends of the structure of our proofs, defined big-Omega, big-Theta and proofs involving general functions.
Proving that a function f is not within big-Oh of a function g is simply proving the negation of the big-Oh statement. So the only really big difference is that we have to assume for all c in the positive real numbers and all B in the natural numbers and we get to choose an x in the natural numbers. Then somehow get n is at least B and that the function f is greater than any c coefficient times the function g.
Something really different this week is that we started omitting most of the bookends. Although those bookends were generally tedious, I have found that they made the proof look more "whole" and now that they are gone, we have a lot more empty space and a sudden conclusion right after we reach the last step of the body. I know that the professor said that this is how proofs are actually written but it still feels uncomfortable looking at it.
Big-Omega is simply establishing a lower bound for a function. As for big-Theta, I have no idea what it is used for. For big-Omega, in the body of its proof, we are instead making a chain of inequalities going the other direction from that of big-Oh. The rest is fortunately the same as big-Oh.
Proving and disproving big-Oh and big-Omega with general functions is similar to with any other functions. Really, the only difference is that we use generic functions that are bounded above or below another function.
For extra insight on Big-Oh and the likes, see this person's post.
Sunday, November 16, 2014
Days of Big-Oh (Week 9)
I felt like I had a better understanding of the current material in Week 9. Suddenly, Big-Oh seems so much less complicated once we started proving functions are within big-Oh of another function. It's a lot clearer when we say that a function f is within Big-Oh of another function g means that after some break point along the x-axis of a graph, all y-axis values of a function f will be the same or less than that of the other function g. This is also a great way to see what it means for a function f to be "bounded" under a function g.
I was surprised by how short and clear the example for proving 3n^2 + 2n in big-Oh of n^2 was. When we started with the proof structure, I made sure to leave a lot of space in between before the concluding line. Then the professor simply wrote the body in 3 lines. I can say that I didn't see that coming. Now that I am looking back at my notes, I can see a large gap of white space in the proof which is filled with doodles to take up the rest of the space.
One thing that was not as clear to me however was choosing the B. I can see we simply choose c to be whatever coefficient is in front of the n^2 after we added up all terms in term of n^2. To try to figure this out, I looked over two of the example proofs where B was chosen to equal 0 in one and 1 in the other. I noticed that in the second proof (3n^2 + 2n + 5 in big-Oh of n^2), that there was a commented part saying that n must be at least 1. So that means B must be based on this assumption made during the chain of inequalities. I also noticed that we tend to choose B = 0 when trying to establish an upper bound for functions without a constant. However, when constants are introduced, B cannot just be 0 anymore. This is from only examining three proofs however, so I cannot simply generalize it.
Overall, I found Week 9 is be much more explanatory than its preceding week. The week was shorter because of the test on Wednesday but I still felt like I learned more in the two days than all other days prior that dealt with big-Oh.
I was surprised by how short and clear the example for proving 3n^2 + 2n in big-Oh of n^2 was. When we started with the proof structure, I made sure to leave a lot of space in between before the concluding line. Then the professor simply wrote the body in 3 lines. I can say that I didn't see that coming. Now that I am looking back at my notes, I can see a large gap of white space in the proof which is filled with doodles to take up the rest of the space.
One thing that was not as clear to me however was choosing the B. I can see we simply choose c to be whatever coefficient is in front of the n^2 after we added up all terms in term of n^2. To try to figure this out, I looked over two of the example proofs where B was chosen to equal 0 in one and 1 in the other. I noticed that in the second proof (3n^2 + 2n + 5 in big-Oh of n^2), that there was a commented part saying that n must be at least 1. So that means B must be based on this assumption made during the chain of inequalities. I also noticed that we tend to choose B = 0 when trying to establish an upper bound for functions without a constant. However, when constants are introduced, B cannot just be 0 anymore. This is from only examining three proofs however, so I cannot simply generalize it.
Overall, I found Week 9 is be much more explanatory than its preceding week. The week was shorter because of the test on Wednesday but I still felt like I learned more in the two days than all other days prior that dealt with big-Oh.
Sunday, November 9, 2014
Worst Case Scenario (Week 8)
I have neglected to post anything for a while because I had been preoccupied with studying for multiple tests and as such simply forgot about this.
All throughout week 8, I really had no idea what I was doing anyways, so I wouldn't have had much to say. Generally speaking, I didn't understand how Big O works and what we were even trying to prove. The counting using tick marks beside each line of a search or sort algorithm seemed really strange and I couldn't see the purpose in counting steps of such algorithms. I knew that we wanted to determine the worse case which would be the scenario in which the program takes the most number of steps to execute. In the linear search algorithm, that would be if the item being searched for isn't actually in the list at all. In which case, the program will have to loop through every item in a list L until it reaches the end to confirm that the item was not found.
One of the things that threw me off was the counting of the while loops. It just looked like a bunch of mismatched i's and j's to me. Another thing was proving that the worst case of insertion sort is within Big O of n^2. The only thing that I got from that is the basic proof structure. The thinking section in the middle did not make sense to me. I was simply copying notes down in class. I guess the most confusing part was the listing of the contributions of each line and then suddenly going to some sort of equations of n. The Omega part was strange too.
I decided to let myself naturally learn this concept over time like I always do for things I don't understand right away. So, I left all of this stuff alone until the following tutorial. As my TA went over the tutorial question sheet, I began to felt that it seemed simpler than what we did in lecture. However, that was only because the tutorial questions didn't actually talk about Big O, since it was only on counting steps which seemed simple enough this time around. I realized that each line within a while loop will iterate once per counting variable outside of it, generating steps equal to the number of lines inside of it times the number of iteration plus one for the last checking of the loop before it stops executing.
Fortunately, things became a little clearer in week 9.
All throughout week 8, I really had no idea what I was doing anyways, so I wouldn't have had much to say. Generally speaking, I didn't understand how Big O works and what we were even trying to prove. The counting using tick marks beside each line of a search or sort algorithm seemed really strange and I couldn't see the purpose in counting steps of such algorithms. I knew that we wanted to determine the worse case which would be the scenario in which the program takes the most number of steps to execute. In the linear search algorithm, that would be if the item being searched for isn't actually in the list at all. In which case, the program will have to loop through every item in a list L until it reaches the end to confirm that the item was not found.
One of the things that threw me off was the counting of the while loops. It just looked like a bunch of mismatched i's and j's to me. Another thing was proving that the worst case of insertion sort is within Big O of n^2. The only thing that I got from that is the basic proof structure. The thinking section in the middle did not make sense to me. I was simply copying notes down in class. I guess the most confusing part was the listing of the contributions of each line and then suddenly going to some sort of equations of n. The Omega part was strange too.
I decided to let myself naturally learn this concept over time like I always do for things I don't understand right away. So, I left all of this stuff alone until the following tutorial. As my TA went over the tutorial question sheet, I began to felt that it seemed simpler than what we did in lecture. However, that was only because the tutorial questions didn't actually talk about Big O, since it was only on counting steps which seemed simple enough this time around. I realized that each line within a while loop will iterate once per counting variable outside of it, generating steps equal to the number of lines inside of it times the number of iteration plus one for the last checking of the loop before it stops executing.
Fortunately, things became a little clearer in week 9.
Subscribe to:
Posts (Atom)