Algorithm analysis – Big O notation


Continuing from my previous post on performance analysis of algoritms, I decided to plot the CPU-time over the size of the problem, that is, the number of cells.

The two graphs above, both plotted ‘log-log’, demonstrate a straight line.  A straight line on a log-log plot is a clear signature of a Power-law, that is, something growing with the power of something else.

So, the blue line in the two graphs above shows the actual measured data points, i.e. results from my simulations. The red line show my attempt to fit a power function to the simulation data.

As can be seen from the plots, the data and the mathematical function concur almost perfectly.

Conclusions ? Obvious. The execution time of the simulation is dependent by power of 4 on the side of the matrix, and by power 2 on the number of cells.

In the next post, I will show how to improve – optimize – the performance of the simulation.

(btw, I’m very proud of the LaTex legends in the graphs! 🙂


About swdevperestroika

High tech industry veteran, avid hacker reluctantly transformed to mgmt consultant.
This entry was posted in development, software and tagged , , , . Bookmark the permalink.

Leave a Reply

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

You are commenting using your 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