How would you go about comparing two proposed algorithms for sorting an array of integer?

Answer 1

This is a broad question. I am assuming you are wanting to compare the speed of each algorithm and there are two ways to measure this:

1. Run both algorithms on the same machine and see how the time compares for different input sizes e.g. start with 100,1000,100,000 etc.

2. The more useful measure would be to attain it's asymptotic run time complexity. This is a mathematical technique that doesn't care about the machines an algorithm might run on but asks a more general question of "How does the time cost of the algorithm scale with respect to the input size". We usually want to know how it scales for the worst-case but we can also calculate the average-case and the best-case complexity. i.e. The best-case input for a sorting algorithm would be when the array (or whatever data structure you use) is already sorted. The worst case depends on how the algorithm works but basically describes when the input is in the worst possible order. Two popular sorting algorithms: Insertion sort runs at O(n^2) and merge sort runs at O(n log n) for worst-case input.

The notation used here is called Big-O notation (Have a look at a definition of this). Using an extremely dumbed down explanation:

What this means is that as n tends to infinity i.e. as the input of the algorithm increases to infinity (in our case the number of things to sort = n) - The time it takes the algorithm to complete grows roughly proportional to some function of n:

Growth/Time complexities from best to worst:

constant time/no growth: Means the time is always the same for any value of n and is O(1),

logarithmic time: O(log n)

linear time: O(n)

linearithmic time: O(n log n)

quadratic time: O(n^2)

cubic time: O(n^3)

exponential time: O(2^n)

To attain this growth rate we need to first count how many "steps" our algorithm takes in the worst-case. This could give you something like T(n) = n^2 + n + 5. Where T(n) is a function to calculate the number of steps taken. Now, you can prove that T(n) = O(n^2) formally by following the definition of big O and providing a proof by induction but that would be going too far for this simple example. Instead, we will skip the proof and just take the most dominating term and ignore constants and lower order terms. So, in this case we throw away the constant 5 and we ignore the n because once n gets to a sufficiently large value the n^2 part of our function will dominate to the point that the n and the constant will barely have any significance in the growth. You will have to look at some examples for how you count the number of steps but basically you are counting how many times the algorithm loops or repeats a certain computation. Then based on the function T(n) you came up with - You could guess that the complexity is O(highest order term in T(n)) and provide a proof.

Constant factors can still be important though. Just because we throw them away doesn't mean they don't matter in some cases. i.e. if you have 2 algorithms that run at O(n) then the algorithm with lower constant factors is probably a better choice. Also, going back to merge sort and insertion sort, even though merge sort scales better because it is logarithmic and insertion sort is quadratic - insertion sort is still better for smaller input sizes up until a certain point. Merge sort has high constant factors that are more noticeable at smaller values of n . However, for a certain value of n and above, merge sort will then be the much better choice. This is just an example where you might have to look at things like constant factors and other things other than the asymptotic complexity of 2 algorithms.