In this week's lecture we started an exciting new chapter, which is about worst case. Worst case is the measurement of the complexity of a program. It count on how many steps it takes for a program to be executed. There are two types of worst case, the first is the worst case for a program is by finding the upper bound of the steps the program need for it to be executed, and the second worst case for a program is by finding the lower bound of the steps the program need for it to be executed.
As we can see from the picture below, these two cases can be written using qualifiers and implication:
 |
| (From course note chapter 4, slide 3) |
Upper bound (big-O) is the worst maximum steps the program needs to be executed. where the exist a c and a B, and by showing that if the B is smaller than n implies the worst case of n is smaller than c*n we can find a function which will be the maximum number of steps it takes for the program to execute.
Lower bound in the other hand is the max minimum steps it takes for the program to execute. The only thing changed between this and the previous statement is that this time B is smaller than n implies the worst case of n is bigger than c*n.
To conclude this week's lesion is that to be honest I personally don't quite fully understand this new concept of big-O at this moment, so I can really say that much, but I think as I get more practice I will get a better understanding of it for sure.
No comments:
Post a Comment