Scalability and performance are often used interchangeable but they are very different. The resource consumption of a program is its performance. So performance looks at a specific part of a program, say the user activating an action and tries to fix the input and circumstances.
Scalability defines how the resource consumption of a program changes when additional resources are added or the input size increases. So a program can have good performance (it runs fast) but when the load increases it can behavely badly (a bad scalability). Take bubble sort for example. Since the algorithm has low overhead it runs fast with small arrays but when the arrays get bigger the runtime gets worse. It doesn’t scale.
There are many ways to improve scalability here we look at one particular: reducing algorithmic complexity. The time complexity of an algorithm is measured with the big T notation. The T notation describes the time behavior of the algorithm when the input size changes. Say you have an algorithm that takes n objects and needs 4 times as long with an overhead of 2. This would be:
T(n) = 4n + 2
Often the correct numbers are not necessary, you just want to have a magnitude. This is where the big O notation comes into play. It describes the asymptotical upper bound or just the behaviour of the fastest growing part. In the above case this would be:
T(n) = 4n + 2 = O(n)
We call such an algorithm linear because the resource consumption grows linear with the increase in input size. Why does this matter? Let’s look at an example.
Say we have a list of numbers and want to know the highest. How long would this take? A straight forward implementation would look like this:
int max = Integer.MIN_VALUE;
for (int number : list) {
if (number > max) {
max = number;
}
}
So we need if the size of the number list is n we need n compare operations. So our algorithm is linear. What if we have two lists of length n? We just our algorithm twice and compare both maximums so it would be
T(n) = 2n + 1 = O(n)
also linear.
Why does this all matter? If our algorithm runs quadratic, so O(n^2) and our input size is n = 1000, we need a multitude of 1 million operations. If it is linear it just needs a multitude of 1000 operations, much less. Reducing the complexity of an algorithm can be business critical or the difference between getting an instant result or losing a customer because he waited too long.
Time complexity isn’t the only complexity you can measure other resources like space can also be measured with big O. I hope this clears some questions and if you have further ones please feel free and leave a comment.
Schneide Blog 