We finally have an answer to these pressing questions. I introduce to you, Big O, Big Θ and Big Ω. These three notations provide us with a good estimate of how slow (or fast!) our programs will run given a large enough input in the worst case.
Big O is used to describe an upper bound on the runtime. This can be extremely useful depending on how fast your runtime grows with the input. If you have a program that runs in O(n!) time for example, you're going to want to leave your program running overnight, possibly for days.
When I ran bogosort during Lab 8 it took 35 minutes to sort a 10 item list. Big O can help prevent that awkward situation where you want to leave it running, but you also want to be there to see it finish and you're not sure how long it will take.
Visually, and mathematically Big-O provides us with an upper bound by giving us a function, that when multiplied by a constant will bound the runtime from above, or inuitively, our runtime will grow no faster than g(n).
The other two boundaries can be even more useful than Big-O. Big Ω provides us with a lower bound on runtime. Rather than giving us a general idea on the maximum amount of time it will take, Big-Ω instead tells us a lower bound. Given an input of size n, some constant times g(n) will make it grow no faster than our runtime.
Finally, Big Θ provides us with perhaps the most useful boundary on the runtime. This tells us that the runtime of our algorithm grows in the same way as some function g(n), essentially bounding it from above and below.
These three notations are an incredibly useful tool under the right circumstances and are no doubt something every programmer should learn at some point. No matter how slow or fast your program is, its still nice to know whether it will finish in the blink of an eye, or whether it will finish long after the heat death of the universe.
No comments:
Post a Comment