Wednesday 3 December 2014

Visualizing Big-O

When first introduced to the formal definition of Big-O, -Omega, and -Theta, it can be a little daunting to absorb everything and understand them. At least I admit that I was overwhelmed by all of the information. So how does one compartmentalize these definitions, and use them for algorithm analysis and proofs?

I don't think there is only one way, instead different people learn through different techniques. However, what works for me is to visualize the definitions in terms of graphs rather than focus on the definitions, which express the same information anyways. For Big-O, I imagine two curves that grow in different rates, and a point on the x-axis as the 'breakpoint', such that beyond that point, one curve is always slower at growth than the other. It goes to reason that that curve is in the Big-O of the faster growing curve.

Now that we understand Big-O, the scaffold is set, and we can easily understand Big-Omega, with just one minor alteration. Instead of saying that the slower curve is in Big-Omega, we say that the faster curve is in Big-Omega. That effectively makes the curve an upper-bound. Finally, Big-Theta is simply the conjunction between Big-O and Big-Omega.

As mentioned before, we use Big-O notation to help us explain the complexity of an algorithm. In reality, we want algorithms that run in O(n) or O(log n), and never O(n^2) or O(n^3), because the run-time would grow exponentially based on n.

No comments:

Post a Comment