101 Ways To Skin A Cat

Figuratively speaking, of course. I’m against animal cruelty. However, in this article we will explore other ways to compute algorithmic complexity. In a previous post, we computed the running time of the code below:

for(int i=0;i<10;i++){
   for(int j=0;j<i;j++){
     for(int k=0;k<j;k++){
         System.out.println("Hello World");

Now that we learned about the Big Oh, we don’t need to know exactly how many times the “Hello World” will execute. We just need to determine the asymptotic behavior of the algorithm. To do this, we will now compute the running time of the above code snippet using elementary calculus.

In the previous post, we came up with an expression of the running time of the code snippet as

\displaystyle C = \frac{1}{2} \Big( \sum_{i=1}^n i^2 + \sum_{i=1}^n i \Big)

We know that the second term above is just

\displaystyle \frac{n(n+1)}{2}

Also, our derivation of the sum of the first term was quite involved so we will try to avoid that as much as possible. If you take a look at the figure below, you can see the graph of f(x) = x^2. I have to mention that this figure was created using OmniGraphSketcher for Ipad.

You can also see rectangles shaded in blue. These rectangles are of width 1 unit and the height of each rectangle is the number above it. Therefore, the area of each rectangle is numerically equal to the height. As you can see from the figure, the total area of the rectangles from 1 to 4 is equal to 1 + 4 + 9 + 16 = 1^2 + 2^2 + 3^2 + 4^2 = \sum_{i=1}^4 i^2. You can also observe that this area is less than the area under the curve, the area indicated in gray. The area under the curve is equal to the proper integral of x^2 evaluated from x=1 to x=5, or symbolically as

\displaystyle \int_1^5 x^2 dx

You might want to ask yourself why the upper limit of integration is x=5 and not x=4.

As can be seen clearly in the figure, the total area of the rectangles is less than the area under the curve, or

\displaystyle \sum_{i=1}^n i^2 \le \int_1^{n+1} x^2 dx

for some finite number n.

Performing the integration and substituting the limits, we get

\displaystyle \sum_{i=1}^n i^2 \le \int_1^{n+1} x^2 dx = \frac{1}{3} x^3\Big|_1^{n+1}
\displaystyle = \frac{1}{3} \Big[ (n+1) ^3 -1 \Big]

Combining this result with C above, we get

\displaystyle C = \frac{1}{2} \Big( \sum_{i=1}^n i^2 + \sum_{i=1}^n i \Big) \le \frac{1}{3} \Big[ (n+1) ^3 -1 \Big] + \frac{n(n+1)}{2}
\displaystyle = \frac{2n^3 + 9 n^2 + 9 n}{6}
\displaystyle < \frac{9n^3 + 9 n^2 + 9 n}{6} < \frac{9}{6}\Big( n^3 + n^3 + n^3\Big) < \frac{9}{2} n^3

By taking M = 9/2, we have

\displaystyle  |C| < M\cdot n^3 = O(n^3)

Therefore, the asymptotic complexity of the code snippet is O(n^3).


Published by

Bobby Corpus

Loves to Compute!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s