Week 8: Counting steps and Big-Oh

I have heard of the big-O for a long time, maybe first time in grade 10. At that time, all I knew about it is that it is a tool to measure how fast a program can finish a task. Well, after this week, I have a new understanding of big-O.

Before learning the definition and how to use big-Oh to justify a program, we need to first learn how to count how many steps a program will take. Basically, the outer part of a program, that is, the part not in any loop, will be executed once. If the sentences are in a loop, to calculate the worse case, just multiply the number of steps in the loop with the maximum time the loop will be executed. For example, if there are two sentences in a while loop, and the loop will be executed three times, then the total number of steps should be 2*3=6. Moreover, loop in loop has the same method to calculate.

I think result of counting steps does not have to be unique because you cannot tell how exactly which case the program will choose. And according to the note of the professor, sometimes we just regard 1+2+...+n steps as n+n+...+n=n^2 steps, rather than n(n+1)/2. I think maybe the reason for this is explained when we learn big-Oh later.

Well, big-O is indeed a "tool" to measure a speed of a program, but not like human who measure speed by testing how many things a program can do in one second, it shows us how many steps a program will take to finish a task. More strictly speaking, it tells us how the number of step of that program changes when the input of the program increases. For example, if I want a program to find a book among 100 books, it will take some steps. But if I want it to find another book in 500 books, how many steps will it take? We can say the program is more quickly if the amount of steps doubled than if it was squared. This actually just explained why n^2 and n(n+1)/2 is the same in big-O. When input doubled, the number of steps both squared, with no difference.

Test two is coming, while I read this in a student's slog: "We are not told if we are allowed to bring aid sheet so that I did not prepare one." I think we have been told for several times that we can bring an 8.5*11 aid sheet at the beginning of the lecture. Also, I don't even think an aid sheet is useful. The questions in the test are quite similar to the ones of previous years. If we review them (even not carefully), you can get a good grade. Meanwhile, there is nearly no equations that we need to use during the exam, I'd rather spending time on reviewing other subjects than writing aid sheet.