Algorithms are an integral part of computer science, and in fact our day to day lives. We use algorithms all the time without thinking about it, in a way our brains are wired to figure out solutions to problems. As computer programmers and application developers we need to know how to translate these solutions into code and ideally effective and efficient code.
In this tutorial series I am going to break a bit from my normal C# Google tutorials. Over the last several months I have seen a lot of people talk about algorithm performance and big O. This is something I learned a very long time ago in collage. After more then 20 years a lot of this has become instinct to me rather then something I was doing with direct intent. When designing an algorithm it is best to know exactly what you are doing and why you are doing it. As someone who has been an application developer for more then twenty years somethings become more instinctive and less purposeful. I have always enjoyed writing tutorials so I thought that I would write a tutorial series on this, in order to get it strait in my own head. I intend to put my normal spin on the series. This will be as simple as possible and the examples will just work.
[wp_ad_camp_3]
Algorithm series
- A gentle introduction to algorithms and bigO
- Algorithms Constant Time O(1)
- Algorithms Linear time O(n)
- Algorithms Logarithmic Time O(log n)
- Algorithms Quadratic time O(n2)
What is Quadratic Time?
With Quadratic time an algorithms run time is proportional to the square root of the amount of data. The Big O notation for Quadratic time is O(n2).
Programmatic speaking Quadratic time algorithms are normally denoted by nested for loops. If your array has 10 items and your algorithm is running in Quadratic time your going to be doing 10 * 10 = 100 steps. When we were looking at linear time it was only been 10 steps. So by simply adding one additional item (11 * 11 = 121) you are adding 21 additional checks to your algorithm.
Bubble Sort
Bubble sort is normally the first sorting algorithm we learn. It can be quite simple to understand and implement, however its efficiency is not all that good as we will see.
When I run the above code and give it an unsorted array of 100 items. The results are as follows.
Enter length of array. (int)
100
Array contains ’99’ items.
I preformed ‘4950’ checks
Execution time ‘0’ minutes ‘0’ seconds ‘0’ Milliseconds
That’s not to bad right? Runs quite quickly.
Now lets see what happens When I run the above code and give it an unsorted array of 60000 items. The results are as follows.
Enter length of array. (int)
60000
Array contains ‘59999’ items.
I preformed ‘1799970000’ checks
Execution time ‘0’ minutes ’14’ seconds ‘344’ Milliseconds
Depending upon the speed of your machine it make run faster or slower for you. As you can see the more data I add the slower the algorithm becomes. This is why it is very important to know your data when deciding which algorithm to use. If you know you will never have more then 100 items then using a bubble sort would be fine. However if in a few years your data could grow to a million items using a bubble sort would be a very bad idea.
You also need to consider the speed of the machine. Running this algorithm on my desktop was not a problem what if you were running it on something smaller, would you see a difference?
[wp_ad_camp_5]
Conclusion
You should now understand why it is important to know your data when deciding which type of algorithm to use. The amount of data and the power of the machine that is running the algorithm is very important when deciding which type of algorithm to use. Using a Quadratic time Algorithms O(n2) algorithm to sort 100 items may not seam bad but what if you were running this on an Arduino board?
Join me in the next tutorial Algorithms Logarithmic Time O(log n).