Scalability in computer algorithm

Scalability is always related to something else. So to say a program is 'scalable' is a sloppy term.

• a program can scale with the size of the DB

• a program can scale with the number of (concurrent) users

• a program can scale with the size of the input

• ...

Also what "scales" means is not well defined. It can mean in some cases linear growth, in other cases nearly no increase in processing-time ...

Often it simply means: The user-experience is acceptable even under heavy load or high increase in number of users.

So if someone says a program scales. You should always ask what exactly is meant my it, if the circumstances do not imply what exactly is meant.

The word "scalability" isn't usually applied to algorithms. It's applied to systems or applications, and it refers to how practical it is to expand the deployment of that application or system to handle increasing loads.

If you have a billing system running on a cluster of computers, for example, then you would call it "scalable" if you can easily add more computers to the cluster to accommodate the load when your customer base expands x2, x5, x10, etc, and if the number of computers you require stays proportional to the number of customers.

A system like that might not be scalable, for example, if it was backed by an SQL database and there was a lot of contention between transactions. In a case like that you might not be able to handle more users just be adding more computers, because they'll just end up waiting for each other all the time.

You should be able to provide some clear estimates on how runtime evolves with more data / processing nodes. And usually, this increase should be linear or at most O(n log n) with the amount of data in order for the algorithm to be scalable. With the number of nodes, you'd want to get close to being able to reduce the runtime by m when using m nodes.

Based on above:

• insertion sort is not available - O(n²)
• merge sort is available - O(n log n)